[프로그래머스 코딩테스트] 최소 직사각형(Java)

  문제 설명

  명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.

  아래 표는 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가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.

 

  제한사항

• sizes의 길이는 1 이상 10,000 이하입니다.
  • sizes의 원소는 [w, h] 형식입니다.
  • 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

class Solution {
    public int solution(int[][] sizes) {
        int a = 0;
        int b = 0;
        for (int i = 0; i < sizes.length; i++) {
            int A = Math.max(sizes[i][0], sizes[i][1]);
            int B = Math.min(sizes[i][0], sizes[i][1]);
            a = Math.max(a, A);
            b = Math.max(b, B);
        }
        int answer = a * b;
        return answer;
    }
}

  변수 a와 b를 생성합니다.

  for문이 sizes의 길이만큼 순회합니다.

  변수 A를 생성하고 Math 클래스의 max 메소드를 이용하여 sizes[i][0] 번째 원소와 sizes[i][1] 번째 원소를 비교하여 최댓값을 할당합니다.

  변수 B를 생성하고 Math 클래스의 min 메소드를 이용하여 sizes[i][0] 번째 원소와 sizes[i][1] 번째 원소를 비교하여 최솟값을 할당합니다.

  변수 a에 a와 A 중 큰 값을 할당합니다.

  변수 b에 b와 B 중 큰 값을 할당합니다.

  크기를 구해야 하므로 앞서 구한 최댓값인 a와 b를 곱하여 answer에 할당합니다.

 

  복잡한 코드를 작성하는 것보다 수학적 원리를 이용하거나 사고력을 요구하는 문제가 더 어려운 것 같습니다. 이번 문제의 경우 단순히 가장 넓은 직사각형을 구하는 것이 아닌, 조건을 충족하는 가장 작은 직사각형을 요구합니다. 심지어는 명함을 돌려서 넣을 경우도 생각해야 합니다.

  모든 명함을 넣을 수 있어야 하므로 가로든 세로든 배열에서 가장 큰 값을 기준으로 계산해야 합니다. max 메소드를 이용하여 가장 긴 길이를 구한 것입니다. A는 각 명함에서 가로와 세로 중 긴 부분을 확인합니다. a에서 다시 다른 명함끼리 비교하여 가장 긴 명함의 길이를 찾습니다. 

  앞서 가장 긴 길이를 구했으므로 이를 기준으로 가로와 세로 구분없이 각 명함이 긴 부분끼리 겹쳐 있다고 상상하면 쉬워질 것 같습니다. 상상을 연장하여 이후 풀이를 진행하면 좋습니다. 남은 부분은 명함에서 짧은 부분입니다. 마찬가지로 B는 min 메소드를 이용하여 각 명함에서 가로와 세로 중 짧은 부분을 확인합니다. 그러나 짧은 부분 중에서는 가장 길어야 합니다. 그래야 모든 명함의 크기를 수납할 수 있기 때문입니다. b는 다른 명함끼리 비교하여 명함의 짧은 부분 중 가장 긴 명함의 길이를 찾습니다. 이해가 되지 않는다면 상상을 해보거나, 직접 그려보는 것도 괜찮을 듯합니다.

  아직도 조금 헷갈리는 것 같습니다. 그래서 설명이 더 장황해지는 것 같고. 그래도 제가 이해한 선에서 최대한 자세히 설명해보고자 노력했습니다. 헷갈리는 분들의 이해에 도움이 되었으면 좋겠습니다.