[Level 1] 최소직사각형 - 86491

문제 설명

명함 지갑을 제작하는 회사에서 다양한 크기의 명함을 모두 수납할 수 있는 최소 크기의 지갑을 찾고자 합니다. 이를 위해 모든 명함의 가로 길이와 세로 길이를 조사하였습니다.

아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.

명함 번호 가로 길이 세로 길이

1	60	50
2	30	70
3	60	30
4	80	40

가장 긴 가로 길이와 세로 길이가 각각 80과 70이므로, 80 × 70 크기의 지갑을 만들면 모든 명함을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80 × 50 크기의 지갑으로도 모든 명함을 수납할 수 있습니다. 이때 지갑 크기는 4000(= 80 × 50)입니다.

모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 지갑의 크기를 구하는 solution 함수를 완성하세요.

제한사항

sizes의 길이는 1 이상 10,000 이하입니다.
sizes의 원소는 [w, h] 형식입니다.
w와 h는 1 이상 1,000 이하의 자연수입니다.

입출력 예

sizes result

[[60, 50], [30, 70], [60, 30], [80, 40]]	4000
[[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]]	120
[[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]]	133

입출력 예 설명

예제 1

문제 예시와 같습니다.

예제 2

3번째 명함(가로: 8, 세로: 15)이 가장 크므로, 지갑의 크기는 120(= 8 × 15)입니다.

예제 3

모든 명함을 포함하는 가장 작은 지갑의 크기는 133(= 19 × 7)입니다.

출처

프로그래머스 코딩 테스트 연습: https://school.programmers.co.kr/learn/challenges

문제를 풀기 전 사고 과정

문제를 해결하기 위해 다음과 같은 사고 과정을 거쳤습니다:

명함을 가로로 눕혀 수납할 수 있구나
가로의 길이가 세로의 길이보다 짧으면 값을 바꾼다.
모든 명함을 비교하여 가로와 세로의 최대값을 찾는다.
최종적으로 최대 가로 길이와 최대 세로 길이를 곱하여 지갑 크기를 결정한다.

C++ 풀이 전 swap 함수 소개

1. std::swap 함수란?

std::swap은 두 변수의 값을 효율적으로 교환하는 C++ 표준 라이브러리 함수입니다. 사용법은 다음과 같습니다:

#include <iostream>
#include <algorithm>

int main() {
    int a = 10, b = 20;
    std::swap(a, b);
    
    std::cout << "a: " << a << ", b: " << b << std::endl;
    return 0;
}

2. std::swap 활용 예제

std::swap은 정렬 알고리즘에서 자주 사용됩니다. 예를 들어, 선택 정렬에서 최소값과 현재 위치의 값을 교환할 때 유용합니다. 또한, 배열을 회전하거나 특정 조건을 만족하는 요소의 위치를 바꿀 때도 활용할 수 있습니다.

배열 회전 예제

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void rotateArray(vector<int>& arr) {
    for (int i = 0; i < arr.size() / 2; i++) {
        swap(arr[i], arr[arr.size() - 1 - i]);
    }
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    rotateArray(arr);
    
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

위 코드에서는 swap을 사용하여 배열을 반대로 회전시킵니다. 이처럼 swap은 간단하면서도 다양한 상황에서 유용하게 활용될 수 있습니다.

C++ 풀이 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> sizes) {
    int maxWidth = 0;
    int maxHeight = 0;

    for (int i = 0; i < sizes.size(); i++) {
        if (sizes[i][0] < sizes[i][1]) {
            swap(sizes[i][0], sizes[i][1]);
        }
        maxWidth = max(maxWidth, sizes[i][0]);
        maxHeight = max(maxHeight, sizes[i][1]);
    }
    return maxWidth * maxHeight;
}

실행 예제 및 예상 결과

아래 실행 예제는 solution 함수를 호출하여 명함 크기를 계산하는 과정과 결과를 보여줍니다. 이를 통해 코드 실행 흐름을 쉽게 이해할 수 있습니다.

입력:

vector<vector<int>> sizes = {{60, 50}, {30, 70}, {60, 30}, {80, 40}};
cout << solution(sizes) << endl;

출력:

이제 코드 실행 시 예상되는 결과를 직접 확인할 수 있습니다.