문제

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

---

풀이

해결과정

• 명함 회전
  • 각 명함의 가로와 세로를 비교하여 더 긴 쪽을 가로로, 다 짧은 쪽을 세로로 맞추는 것이 유리하겠다고 판단했다.

💻 결과코드

class Solution {
    public int solution(int[][] sizes) {
        int widthMax = 0;
        int heightMax = 0;

        for (int i = 0; i < sizes.length; i++) {
            if(sizes[i][0] < sizes[i][1]) {
                widthMax = Math.max(sizes[i][1], widthMax);
                heightMax = Math.max(sizes[i][0], heightMax);
            } else {
                widthMax = Math.max(sizes[i][0], widthMax);
                heightMax = Math.max(sizes[i][1], heightMax);
            }
        }

        return widthMax * heightMax;
    }
}

💻 코드 리팩토링

다른 사람들의 코드를 참고하여 코드를 리팩토링 해봤다.

class Solution {
    public int solution(int[][] sizes) {
        int widthMax = 0;
        int heightMax = 0;

        for (int i = 0; i < sizes.length; i++) {
            // 각 명함의 가로와 세로 중 큰 값을 widthMax와 비교, 작은 값을 heightMax와 비교
            int longer = Math.max(sizes[i][0], sizes[i][1]);
            int shorter = Math.min(sizes[i][0], sizes[i][1]);
            
            widthMax = Math.max(longer, widthMax);
            heightMax = Math.max(shorter, heightMax);
        }

        return widthMax * heightMax;
    }
}

• 결과적으로 Math를 통한 값 비교를 2번 수행하게 되는데, 이걸 한문장에서 끝내는게 더 좋아보였다.

class Solution {
    public int solution(int[][] sizes) {
        int length = 0, height = 0;
        for (int[] card : sizes) {
            length = Math.max(length, Math.max(card[0], card[1]));
            height = Math.max(height, Math.min(card[0], card[1]));
        }
        int answer = length * height;
        return answer;
    }
}

---

📗 완전 탐색

완전탐색 알고리즘이란?

• 완전탐색은 간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법이다.
  • 즉, 무식하게 가능한 거 다 해보겠다는 방법을 의미한다.
• 이 방법은 무식하게 한다는 의미로 "Brute Force"라고도 부르며, 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다.

완전탐색 활용 방법

1. Brute Force 기법 - 반복 / 조건문을 활용해 모두 테스트하는 방법
2. 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
3. 재귀 호출
4. 비트마스크 - 2진수 표현 기법을 활용하는 방법
5. BFS, DFS를 활용하는 방법

---

Reference

• 알고리즘 - 완전탐색(Exhaustive Search)