[99클럽 코테 스터디] 16일차 TIL 완전탐색

 

 

오늘의 문제는 프로그래머스

 

최소직사각형 

 

 

문제

 

 

문제 설명 

 

주어진 이차원 배열 sizes는 각 명함의 가로와 세로 길이를 담고 있습니다. 

모든 명함을 담을 수 있는 크기의 지갑을 만든다고 가정했을 때 가로와 세로 크기를 곱한 최적 지갑 크기를 반환하면 되는 문제입니다. 

예를 들어 sizes가 [[60, 50], [30, 70], [60, 30], [80, 40]] 일 때, 가로의 최대값은 80이고 세로의 최대 값은 70입니다. 하지만 [30,70]의 명함을 가로로 눕혀 지갑에 넣는다고 했을 때 가로의 최대값은 80이고 세로의 최대값은 50이 되므로 이 둘을 곱한 4000을 결과로 반환하면 됩니다. 

 

 

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 37분이 걸렸습니다. 

 

 

 

문제 접근 방식

먼저 이차원 배열을 정렬해줍니다. 기준은 가로가 세로보다 작은 경우, 둘의 순서를 바꾸는 것으로 합니다. 이렇게 하는 이유는 모든 카드의 가로가 세로보다 크거나 같도록 통일하기 위함입니다. 그 다음 가로의 최대값과 세로의 최대값을 구해 둘을 곱한 결과 값을 반환합니다. 

 

 

 

문제 풀이

class Solution {
    public int solution(int[][] sizes) {
        
        int answer = 0;
        
        int maxW = 0;
        int maxH = 0; 
        
        int len = sizes.length; 
        
        for(int i = 0; i < len; i++) {
            if(sizes[i][0] < sizes[i][1]) {
                int temp = sizes[i][0];
                sizes[i][0] = sizes[i][1];
                sizes[i][1] = temp; 
            }
        }
        
        for(int i = 0; i < len; i++) {
            if(sizes[i][0] > maxW) {
                maxW = sizes[i][0];
            }
            if(sizes[i][1] > maxH) {
                maxH = sizes[i][1];
            }
        }
        
        answer = maxW * maxH; 
        
        return answer;
    }
}

 

 

이차원 배열 sizes의 구조 이해하기 

sizes 배열은 이차원 배열입니다. 따라서 sizes[i]는 i번째 카드의 크기를 나타내는 배열입니다.

sizes가 [[60, 50], [30, 70], [60, 30], [80, 40]] 인 경우를 예로 들어보겠습니다. 

sizes[0]은 [60, 50], sizes[1]은 [30,70], sizes[2]는 [60,30], sizes[3]은 [80,40]이 됩니다. 

따라서 sizes[i][0]은 i 번째 카드의 가로 길이를 의미하고 sizes[i][1]은 카드의 세로 길이를 의미합니다. 

 

 

 

배열을 정렬하는 이유 

가로 크기가 세로 크기 보다 작은 경우 둘의 순서를 바꿔주는 부분이 있습니다. 이렇게 정렬하는 이유를 예시를 통해 자세히 알아봅시다. 

sizes가 [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 인 경우를 예로 들겠습니다. 

이 중 가로의 크기가 세로의 크기보다 작은 경우는 [8,15]와 [5,15]입니다. 이 둘을 순서를 바꿔 정렬하면

[[10, 7], [12, 3], [15,8], [14, 7], [15,5]] 가 됩니다. 

여기서 가로의 최대와 세로의 최대를 구하면 15와 8이 됩니다. 

 

 

다른 풀이 알아보기 

아래 코드는 카드의 크기를 전부 순환합니다. 

첫 번째 변수에 가로와 세로 중 큰 값을 선택한 다음 그 중 최대 값을 저장합니다.

두 번째 변수에 가로와 세로 중 작은 값을 선택한 다음 그 중 최대 값을 저장합니다. 

이렇게 하면 length에는 모든 값 중 최대값이 저장되고 height에는 작은 값 중 가장 큰 값을 저장하게 되어 최적의 지갑 크기를 구할 수 있게 됩니다. 

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;
    }
}

 

 

 

 

 

 

 

이렇게 오늘 16일차 TIL을 작성해 보았습니다.