[프로그래머스] 86491 최소직사각형 (Lv.1) - 완전 탐색

문제

코드

시도 1 - X

처음 문제를 봤을 땐 모든 경우의 수를 전부 다 확인해서 최적해을 찾아야 하나 생각했다. 그런데 아무리 봐도 시간 복잡도가 말이 안돼서 코드 작성 도중 다른 방법을 생각했다.(-> 시도2)

import java.util.*;
class Solution {
    public int solution(int[][] sizes) {

        int[] size = new int[2]; // 명함 지갑 가로 세로 최댓값

        int maxWidth = findMax(sizes, 0);
        int maxLength = findMax(sizes, 1);
        for (int i = 0; i < sizes.length; i++) {

        }
        return maxWidth*maxLength;

    }

    public int findMax(int[][] sizes, int row) {
        int max = 0;
        for (int i = 0; i < sizes.length; i++) {
            if (sizes[i][row] > max) {
                max = sizes[i][row];
            }
        }
        return max;
    }

    public void swap(int[][] sizes, int i) {
        int tmp = sizes[i][0];
        sizes[i][0] = sizes[i][1];
        sizes[i][1] = tmp;
    }
}

시도 2 - O

• 명함들의 가로, 세로 각각의 최댓값을 구해야 한다.
• 위에서 구한 최댓값들이 최솟값이어야 한다.
  위 두 핵심 조건을 만족하기 위해서는 각 명함의 큰 값을 가로로 모으고, 작은 값을 세로로 모은 후 가로의 최댓값, 세로의 최댓값을 구해야 한다. 즉, 가장 큰 수들의 최댓값, 가장 작은 수들의 최댓값을 구하면 해결되는 문제였다.
• 시간 복잡도: O(n)

import java.util.*;
class Solution {
    public int solution(int[][] sizes) {

        // 각 명함의 가로 세로 길이 중 큰 값을 가로에 넣고 작은 값을 세로에 넣는다.
        for (int i = 0; i < sizes.length; i++) {
            int width = Math.max(sizes[i][0], sizes[i][1]); // 큰 값을 가로
            int length = Math.min(sizes[i][0], sizes[i][1]); // 작은 값을 세로
            sizes[i][0] = width;
            sizes[i][1] = length;
        }
        Arrays.sort(sizes, (o1, o2) -> Integer.compare(o2[0], o1[0]));
        int maxWidth = sizes[0][0];
        Arrays.sort(sizes, (o1, o2) -> Integer.compare(o2[1], o1[1]));
        int maxLength = sizes[0][1];

        return maxWidth * maxLength;
    }
}