프로그래머스 Lv.1 : 최소직사각형 🅾️

[문제]

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

아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.

1	60	50
2	30	70
3	60	30
4	80	40

 

가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.

모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.

프로그래머스

 

[풀이]

이번 풀이는 2가지 방법을 가져와봤다.

첫 번째는 comparator 연습을 위해 구현해 본 방법이고, 두 번째는 내가 생각하는 알고리즘 구현이다.

 

첫 번째 코드

import java.util.*;
class Solution {
    public int solution(int[][] sizes) {
        Arrays.sort(sizes, new Comparator<int[]>(){
            @Override
            public int compare(int[] i1, int[] i2) {
                if(i1[0]<i1[1]) {
                    int tmp=i1[1];
                    i1[1]=i1[0];
                    i1[0]=tmp;
                }
                if(i2[0]<i2[1]) {
                    int tmp=i2[1];
                    i2[1]=i2[0];
                    i2[0]=tmp;
                }
                return i2[0] - i1[0];
            }
        });
        int w=sizes[0][0];
        Arrays.sort(sizes, new Comparator<int[]>(){
            @Override
            public int compare(int[] i1, int[] i2) {
                return i2[1] - i1[1];
            }
        });
        
        return w*sizes[0][1];
    }
}

 

오직 커스텀 정렬로만 해결한 케이스!

분명 카테고리는 완탐인데(??..) 정렬만 했다.

그렇다면 문제의 취지에 따라 완전탐색을 진행해보는건 어떨까 해서, 이 코드에서 멈추지 않고 다른 방법을 모색했다.

 

두 번째 코드

import java.util.Arrays;
class Solution {
    public int solution(int[][] sizes) {
        int[] max=new int[sizes.length];
		int[] min=new int[sizes.length];
		
		for(int i=0;i<sizes.length;i++) {
			int x=sizes[i][0];
			int y=sizes[i][1];
			if(x>y) {
				max[i]=x;
				min[i]=y;
			} else {
				max[i]=y;
				min[i]=x;
			}
		}
		
		Arrays.sort(max);
		Arrays.sort(min);
		
		return max[sizes.length-1]*min[sizes.length-1];
    }
}

 

이 방법은 명함의 가로 길이 배열과 세로 길이 배열을 각각 빼줘서 알고리즘을 구현한 방법이다.

가로 길이, 세로 길이 배열을 따로 만들어주었는데 이름이 max[], min[]인 이유는

사실상 내가 만든 배열이 각 명함의 긴 쪽 길이 배열과 각 명함의 짧은 쪽 배열이기 때문이다.

 

sizes를 탐색하며 각각의 길이 중 긴 쪽의 길이를 max 배열에, 짧은 쪽의 길이를 min 배열에 넣었다.

마지막으로 각각 sort 해주면 명함을 넣을 수 있는 최소 가로 길이와 세로 길이를 구할 수 있다.

 

참고로 효율은 완탐 코드가 더 굿이다.

역시 문제의 취지를 따르는 것이 중요한 것 같다..

실제 코테에서는 알려주지 않으니..

문제를 보고 무슨 알고리즘을 요하는가~에 대해 바로바로 생각할 수 있는 능력을 길러야겠다!