최소직사각형(lv1)

 

문제 설명

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

아래 표는 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 함수를 완성해주세요.

---

제한사항

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

---

입출력 예sizesresult

[[60, 50], [30, 70], [60, 30], [80, 40]]	4000
[[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]]	120
[[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]]	133

---

입출력 예 설명

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

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

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

 

20220825 진행중인 코드

class Solution {
    public int solution(int[][] sizes) {
        int answer = 0;
        return answer;
    }
}

20220830 진행중인 코드

음.. 뭔가 주석을 달면서 하니까 좀 생각이 정리되는듯?..

class Solution {
      /**
     * 최소 직사각형
     * 명함들의 가로세로 크기가 주어지고(직사각형), 모든 명함을 포함하는 최소 직사각형 크기를 구한다.
     * 명함은 회전이가능하다. = 명함의 가로세로 길이가 변경이 된다.
     */
    public int solution(int[][] sizes) {
         /**
         * 20220830
         * 1. 먼저 sizes 배열로부터 가로/세로를 따로 분리한 배열을 구한다.
         * 2. 그 배열로 부터 가로세로의 최댓값들을 구한다.
         * 3. for문을 돌면서. 각 명함들을 회전해서 가로세로가 바뀌었을때 모든 명함을 포함하고 기존 max값보다 작은지 확인한다.
         * 4. 기준에 일치하면 최댓값을 새로 갱신한다.
         * 5. for문을 종료하면 최소값의 가로세로가 나온다!
         * 6. 가로 * 세로(크기)의 값을 반환한다!
         */
        int answer = 0;
        int maxWidth = 0; //최대 폭 (가로)
        int maxHeigth = 0;//최대 높이 (세로)
        int[] widths = new int[sizes.length]; //폭(가로) 배열
        int[] heights= new int[sizes.length];//높이(세로) 배열

        //폭,높이 최댓값 구하기
        for(int i=0; i<sizes.length; i++){
            widths[i] = sizes[i][0];
            heights[i] = sizes[i][1];
            if(maxWidth<widths[i]){
                maxWidth = widths[i];
            }
            if(maxHeigth<heights[i]){
                maxHeigth=heights[i];
            }
        }

        return answer;
    }
}

20220831

음.. 1번째 테스트 케이스는 통과했으나, 2,3번째 테스트 케이스는 통과하지 못했다. 

역시 직사각형을 회전하고 판단? 하는 로직에 뭔가 문제가 있는것 같다.

/**
         * 20220830
         * 1. 먼저 sizes 배열로부터 가로/세로를 따로 분리한 배열을 구한다.
         * 2. 그 배열로 부터 가로세로의 최댓값들을 구한다.
         * 3. for문을 돌면서. 각 명함들을 회전해서 가로세로가 바뀌었을때 모든 명함을 포함하고 기존 max값보다 작은지 확인한다.
         * 4. 기준에 일치하면 최댓값을 새로 갱신한다.
         * 5. for문을 종료하면 최소값의 가로세로가 나온다!
         * 6. 가로 * 세로(크기)의 값을 반환한다!
         */
        int answer = 0;
        int maxWidth = 0; //최대 폭 (가로)
        int maxHeigth = 0;//최대 높이 (세로)
        int[] widths = new int[sizes.length]; //폭(가로) 배열
        int[] heights= new int[sizes.length];//높이(세로) 배열

        //1. 먼저 sizes 배열로부터 가로/세로를 따로 분리한 배열을 구한다.
        //2. 그 배열로 부터 가로세로의 최댓값들을 구한다.
        for(int i=0; i<sizes.length; i++){
            widths[i] = sizes[i][0];
            heights[i] = sizes[i][1];
            if(maxWidth<widths[i]){
                maxWidth = widths[i];
            }
            if(maxHeigth<heights[i]){
                maxHeigth=heights[i];
            }
        }
		//20220831
        // 3.for문을 돌면서. 각 명함들을 회전해서 가로세로가 바뀌었을때 모든 명함을 포함하고 기존 max값보다 작은지 확인한다.
        for(int i=0; i<sizes.length; i++){
            int currentWidth = sizes[i][0];
            int currentHeight = sizes[i][1];
            if(currentWidth<=maxHeigth && currentHeight<=maxWidth){
                int[] tmpWidthArr = Arrays.copyOf(widths,widths.length);
                int[] tmpHeigthArr = Arrays.copyOf(heights,heights.length);
                tmpWidthArr[i] = currentHeight;
                tmpHeigthArr[i] = currentWidth;

                int tmpWidthMax = Arrays.stream(tmpWidthArr).max().getAsInt();
                int tmpHeightMax = Arrays.stream(tmpHeigthArr).max().getAsInt();

                if(maxWidth>tmpWidthMax || maxHeigth>tmpHeightMax){
                    answer = tmpWidthMax * tmpHeightMax;
                }
            }
        }
        return answer;

20220901 완성코드

비지니스 로직 자체에서 결함이 있었다. 

디버깅을 걸면서 보다가, 자연스럽게 내가?... 배열들을 보면서 일케 하면되겠네! 라고 생각이 들자 그걸 코드로 표현했다.

 

성공!!! ㅋㅋㅋ

        /**
         * 20220901
         * 1. 먼저 sizes 배열로부터 가로/세로를 따로 분리한 배열을 구한다.
         * 2. 그 배열로 부터 가로세로의 최댓값들을 구한다.
         * 3. 최댓값 가로(w),세로(h) 중 더 큰 값을 구한다.
         * 4. 더 큰값의 배열을 기준으로 for문을 돌면서 w,h중 더 큰값을 기준 배열로 옮긴다.
         * 5. 바뀐 배열들의 최댓값을 구하고, 크기를 구해서 반환한다.
         */
        int answer = 0;
        int maxWidth = 0; //최대 폭 (가로)
        int maxHeigth = 0;//최대 높이 (세로)

        int[] maxArr;
        int[] minArr;
        int[] widths = new int[sizes.length]; //폭(가로) 배열
        int[] heights= new int[sizes.length];//높이(세로) 배열

        //1. 먼저 sizes 배열로부터 가로/세로를 따로 분리한 배열을 구한다.
        for(int i=0; i<sizes.length; i++){
            widths[i] = sizes[i][0];
            heights[i] = sizes[i][1];
            //2. 그 배열로 부터 가로세로의 최댓값들을 구한다.
            if(maxWidth<widths[i]){
                maxWidth = widths[i];
            }
            if(maxHeigth<heights[i]){
                maxHeigth=heights[i];
            }
        }

        //3. 최댓값 가로(w),세로(h) 중 더 큰 값을 구한다.
        maxArr = maxHeigth > maxWidth ? heights : widths;
        minArr = maxHeigth > maxWidth ? widths : heights;

        //4. 더 큰값의 배열을 기준으로 for문을 돌면서 w,h중 더 큰값을 기준 배열로 옮긴다.
        for(int i=0; i<sizes.length; i++){
            int currentHeight = heights[i];
            int currentWidth = widths[i];

            maxArr[i] = Math.max(currentHeight,currentWidth);
            minArr[i] = Math.min(currentHeight,currentWidth);
        }
        //5. 바뀐 배열들의 최댓값을 구하고, 크기를 구해서 반환한다.
        answer = Arrays.stream(maxArr).max().getAsInt() *  Arrays.stream(minArr).max().getAsInt();

        return answer;

ref

https://school.programmers.co.kr/learn/courses/30/lessons/86491?language=java 

프로그래머스