[프로그래머스] 최소직사각형

 

https://school.programmers.co.kr/learn/courses/30/lessons/86491

프로그래머스

 

프로그래머스에 올라온 완전탐색 기초문제 level 1 문제이다.

보통 완전탐색 문제 해결 방법을 떠올리자면 대표적으로 "dfs" 알고리즘이 있다.

 

문제에 대한 설명을 이어가자면, sizes 2차원 배열에 있는 값들을 참고하여 최소 크기를 만족할 수 있는 직사각형 너비 * 높이 값을 구하는 것인데, 다만 명함의 방향을 바꿔서 가로 <-> 세로 전환이 가능하다는 점이 핵심이다.

 

sizes 2차원 배열을 순차적으로 돌면서, 기존 대로 하였을 때 더 작은 크기의 직사각형을 만들 수 있는지 혹은 180도 바꿨을때 (즉, 가로 세로를 바꿨을때) 더 작은 크기의 직사각형을 만들 수 있는지 체크하면서 값을 업데이트하면 된다.

 

예제 코드는 다음과 같다.

 

class Solution {
    public static int solution(int[][] sizes) {
        int answer = 0;

        int width = sizes[0][0];
        int height = sizes[0][1];

        for (int i = 1; i < sizes.length; i++) {
            int tempWidth = width, tempWidth2 = width;
            int tempHeight = height, tempHeight2 = height;

            tempWidth = sizes[i][0] > width ? sizes[i][0] : width;
            tempHeight = sizes[i][1] > height ? sizes[i][1] : height;

            tempWidth2 = sizes[i][1] > width ? sizes[i][1] : width;
            tempHeight2 = sizes[i][0] > height ? sizes[i][0] : height;

            if (tempWidth * tempHeight < tempWidth2 * tempHeight2) {
                width = tempWidth;
                height = tempHeight;
            } else {
                width = tempWidth2;
                height = tempHeight2;
            }
        }
        return width * height;
    }
}