[프로그래머스] (Java) 최소 직사각형 문제 풀이 (완전탐색)

 

📑 1. 문제설명

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

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

 

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

 

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

 

제한사항

• sizes의 길이는 1 이상 10,000 이하입니다.
  • sizes의 원소는 [w, h] 형식입니다.
  • w는 명함의 가로 길이를 나타냅니다.
  • h는 명함의 세로 길이를 나타냅니다.
  • w와 h는 1 이상 1,000 이하인 자연수입니다.

입출력 예

 

입출력 예 설명

 

입출력 예 #1
문제 예시와 같습니다.

 

입출력 예 #2
명함들을 적절히 회전시켜 겹쳤을 때, 3번째 명함(가로: 8, 세로: 15)이 다른 모든 명함보다 크기가 큽니다. 따라서 지갑의 크기는 3번째 명함의 크기와 같으며, 120(=8 x 15)을 return 합니다.

 

입출력 예 #3
명함들을 적절히 회전시켜 겹쳤을 때, 모든 명함을 포함하는 가장 작은 지갑의 크기는 133(=19 x 7)입니다.

---

💡 2. 접근방식

완전탐색

틀린코드

처음에는 sizes[][]를

가로 기준(sizes[][0])으로 내림차순 정렬한 것을 새로운 배열 a에 담아준다.

세로 기준(sizes[][1])으로도 내림차순 정렬해서 새로운 배열 b에 담아 준다.

그리고 가로길이를 담아줄 w 변수, 세로 길이 담아줄 h변수를 선언한다.

그리고 a와 b 배열의 최댓값을 변수aMax와 bMax에 담아주고 그 둘을 비교해서

가로의 길이가 길면, aMax가 w 값이 되고, b를 순회하면서 aMax보다 작은 값을 h에 대입해 주면 될 거라고 생각 했다.

만약 세로의 길이가 길면, bMax가  h값이 되고 a를 순회하해서 bMax보다 작은 값이 나오면 w에 대입하자고 생각했다.

 

근데 코드를 짜다 보면

위의 방식대로 하면 시간을 많이 잡아먹고, 비효율적이다.

일단 정렬한 배열 복사도 바로 안 됨 

파이썬처럼 바로 정렬해서 새 배열에 넣어주는게 안된다고 함

그 이유는 배열 정렬한 값을 반환하는게 아니라 직접 배열을 수정하기 때문이다.

그래서 일일이 담아주건지, 오름차순으로 정렬한 걸로 reverse(배열반전) 해 주어야 한다.

 

Arrays.sort() 메서드는 배열을 직접 변경하지만 반환값이 없기 때문에 a = Arrays.sort(a, ...)와 같은 방식으로 사용하면 오류가 발생합니다. 이는 Arrays.sort()가 배열을 정렬한 후 수정된 배열을 반환하지 않기 때문입니다. 즉, Arrays.sort()는 정렬된 배열을 **"수정"**하는 동작을 수행하지만, 그 결과를 반환하지 않습니다.

 

 

 

import java.util.*;

class Solution {
    public int solution(int[][] sizes) {
        // 가로와 세로 길이를 각각 저장할 배열 생성
        int[][] a = new int[sizes.length][2];
        int[][] b = new int[sizes.length][2];
        
        // sizes 배열을 a, b 배열로 복사
        for (int i = 0; i < sizes.length; i++) {
            a[i][0] = sizes[i][0]; // 가로
            a[i][1] = sizes[i][1]; // 세로
            b[i][0] = sizes[i][0]; // 가로
            b[i][1] = sizes[i][1]; // 세로
        }
        
        // a 배열을 가로 기준 내림차순 정렬
        // a[i][0] (가로) 기준 내림차순 정렬
        Arrays.sort(a, (x, y) -> Integer.compare(y[0], x[0]));  
        
        // b 배열을 세로 기준 내림차순 정렬
        // b[i][1] (세로) 기준 내림차순 정렬
        Arrays.sort(b, (x, y) -> Integer.compare(y[1], x[1]));  
        
        
        // aMax와 bMax를 각각의 배열에서 최댓값을 찾아 할당
        int aMax = a[0][0]; // a 배열에서 가로 기준 최대값
        int bMax = b[0][1]; // b 배열에서 세로 기준 최대값
        
        // 가로와 세로를 담을 변수
        int w = 0, h = 0;
        
        // 가로가 더 긴 경우
        if (aMax > bMax) {
            w = aMax;
            // b 배열을 순회하면서 aMax보다 작은 값을 h에 대입
            for (int i = 0; i < b.length; i++) {
                if (b[i][1] < aMax) {
                    h = b[i][1];
                    break;
                }
            }
        } 
        // 세로가 더 긴 경우
        else {
            h = bMax;
            // a 배열을 순회하면서 bMax보다 작은 값을 w에 대입
            for (int i = 0; i < a.length; i++) {
                if (a[i][0] < bMax) {
                    w = a[i][0];
                    break;
                }
            }
        }
        
        // 지갑 크기 계산 후 반환 (w * h)
        return w * h;
    }
}

 

그리고 차라리 a,b배열을 1차원 배열로 선언해서 다시 해 보기로 했다. 

import java.util.*;

class Solution {
    public int solution(int[][] sizes) {
        // 가로와 세로 값을 각각 1차원 배열로 저장
        int[] a = new int[sizes.length];
        int[] b = new int[sizes.length];
        
        // 가로와 세로 값을 a, b 배열에 저장
        for (int i = 0; i < sizes.length; i++) {
            a[i] = sizes[i][0];  // 가로
            b[i] = sizes[i][1];  // 세로
        }
        
        // 가로 배열을 내림차순으로 정렬
        Arrays.sort(a);
        for (int i = 0; i < a.length / 2; i++) {
            int temp = a[i];
            a[i] = a[a.length - 1 - i];
            a[a.length - 1 - i] = temp;
        }

        // 세로 배열을 내림차순으로 정렬
        Arrays.sort(b);
        for (int i = 0; i < b.length / 2; i++) {
    		int temp = b[i];
    		b[i] = b[b.length - 1 - i];
    		b[b.length - 1 - i] = temp;
		}
        
        int maxW = a[a.length - 1];  // 가로의 최댓값
        int maxH = b[b.length - 1];  // 세로의 최댓값
        
        // 가로와 세로의 최댓값을 구할 변수
        int w = 0;
        int h = 0;
        
        // 가로와 세로의 최댓값을 비교해서 지갑의 크기 계산
        if (maxW > maxH) {
            w = maxW;
            for (int i = 0; i < b.length; i++) {
                if (b[i] <= maxW) {
                    h = b[i];
                    break;  
                }
            }
        } else {
            h = maxH;
            for (int i = 0; i < a.length; i++) {
                if (a[i] <= maxH) {
                    w = a[i];
                    break;
                }
            }
        }
        
        // 지갑 크기 계산 후 반환 (w * h)
        return w * h;
    }
}

 

 

코드가 길어지면서부터... 아 이렇게 풀면 하루 종일 걸리겠구나 이거 아니네 했지만

그래도 한 번 생각한거 마무리는 해 보고 싶은 마음에 이것저것 시도 해 보았으나 결국 안됨

무튼 어떤 부분이 정확히 잘못됬는지 모르겠는데 시간이 없어서 나중에 고쳐보도록 하겠음~

 

알고리즘 문제 풀다 보면 신기한 건

아! 이 문제 쉽네 금방 하겠다 하는 거라도 안 되는 경우가 있다

그리고 아 이건 문제 이해하기도 어렵네 했는데 징검다리문제처럼 

문제만 이해하면 코드는 간단한 것도 있다.

 

알고리즘은 최고의 천재 수학자들이 발견해서 노벨상 받은건데

당신이 0.00001프로의 천재가 아니라면 당연히 어려울 수밖에 없고 한번에 최고의 로직을 찾아내는 것은 거의 불가능하다.

 

문제 유형별로 다른 사람들은 어떻게 풀었는지, 어떻게 해야 가장 효율적으로 푸는 건지

평소에 좋은 코드를 많이 봐서 해당 문제에 적용 가능한 최고의 알고리즘을 빨리 찾는 것이 잘 하는 길이다.

남의 코드 리딩하면서 배우자!! 

---

⭐ 3. 코드

그래서 다른 사람들이 어떻게 푸는 지 살펴 보고 코드를 써 봤습니다.

이해완료

 

각 sizes[i]를 순회하며 width와 height를 비교해 더 큰 값을 가로, 작은 값을 세로로 설정해준다.

루프 돌면서 각 요소의 가로값과 세로값 중 큰 값은 w에 작은 값은 h에 담아 주었다.

그리고 가로 최대값과 세로 최대값과 비교 해 가며 maxW랑 maxH를 업뎃해주는 방식이다.

 

import java.util.*;

class Solution {
    public int solution(int[][] sizes) {
        int maxW = 0;
        int maxH = 0;
        // 각 명함의 가로와 세로 중 더 큰 값을 w로, 작은 값을 h로 설정
        for(int i = 0; i < sizes.length; i++) {
            int w = Math.max(sizes[i][0], sizes[i][1]);
            int h = Math.min(sizes[i][0], sizes[i][1]);
            // 가로 최대값 갱신
            maxW = Math.max(maxW, w);
            // 가로 최소값 갱신
            maxH = Math.max(maxH, h);
        }
        return maxW * maxH;
    }
}

머리 쓰지 말고 있는거 쓰자

시간 낭비 하지 말고

남이 한거 보고 배우자

 

내가 생각한 데로 풀어보려고 노력하면서 알게된 사실은

알고리즘은 사실 항상 문제 유형과 답이 정해져 있다.

내가 풀다가 코드 길어지거나 막힌다? 

그건 절대 효율적인 게 아니라는 것이다.

거기에 시간 낭비 하지말고

 

그래서 남들은 어떻게 했는지 찾아 보고 프그 다른사람의 풀이에서 좋아요 가장 많은 거 보자

남들 푸는 거 봐도 다 같은 방식으로 풀었다.

왜 ? 이렇게 하는게 시간도 아끼고 가장 간단하니까

 

👍🏻좋아요 가장 많이 받은 풀이

이번 문제에서는 min, max 쓰는 법이 관건임 ㅎㅎㅎ

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

import java.util.*;
class Solution {
    public int solution(int[][] sizes) {
        return Arrays.stream(sizes).reduce((a, b) -> new int[]{
                Math.max(Math.max(a[0], a[1]), Math.max(b[0], b[1])), Math.max(Math.min(a[0], a[1]), Math.min(b[0], b[1]))
        }).map(it -> it[0] * it[1]).get();
    }
}

---

👉🏻 4. 같은 유형 문제(완전탐색)

[프로그래머스] (Java) 최소 직사각형 문제풀이 (완전탐색)

 

---

 

TMI

어휴 명함 크기는 제발 하나로 좀 통일하자^^;;