[알고리즘/Programmers] LV1. 최소직사각형 (Java)

 

오늘의 학습 키워드

• 완전탐색 해야할 줄 알았더니 사고력 문제..🤷🏻‍♀️

오늘의 회고

1. 문제

문제 URL

프로그래머스

2. 해결 방안

성공 코드

    public static int solution(int[][] sizes) {

        // 초기화 주의 : 가로 세로 중 최대값이 가로여야 하므로, 단순히 sizes의 첫번째 값들을 넣으면 안된다.
        int widthMax = 0;
        int heightMax = 0;

        for(int i=0; i< sizes.length; i++) {
            // 가로,세로 중 더 큰값
            int width = Math.max(sizes[i][0], sizes[i][1]);
            int height = Math.min(sizes[i][0], sizes[i][1]);

            widthMax = Math.max(widthMax, width);
            heightMax = Math.max(heightMax, height);
        }

        return widthMax * heightMax;
    }

• 케이스를 돌면서 가로,세로 중 더 큰 값을 가로로 맞추고(혹은 세로로. 통일만 되면 됨) 케이스 중 가로, 세로의 최대값을 찾으면 된다
• 최대의 가로, 세로 곱한 너비 값 반환.
• 초기화 시킬때도 주의한다. 가로 세로 중 최대값을 가로로 맞출거기 때문에 첫번째 요소의 가로, 세로를 그대로 초기화 시키는 것도 안된다. 그냥 0으로 초기화 시키면 깔끔.

실패 코드

    public int solutionX(int[][] sizes) {

        // 최소값 rows, cols 세팅
        int[] rows = new int[sizes.length];
        int[] cols = new int[sizes.length];
        for(int i=0; i<sizes.length; i++) {
            rows[i] = sizes[i][0];
            cols[i] = sizes[i][1];
        }
        Arrays.sort(rows);
        Arrays.sort(cols);

        for(int i=0; i<rows.length; i++) {
            for(int j=0; j<cols.length; j++) {
                if(!rowColCheck(sizes, rows[i], cols[j])) {
                    continue;
                }
                return rows[i] * cols[j];
            }
        }

        return -1;
    }

    private boolean rowColCheck(int[][] sizes, int row, int col) {

        for(int i=0; i< sizes.length; i++) {
            int caseRow = sizes[i][0];
            int caseCol = sizes[i][1];

            if(caseRow <= row && caseCol <= col) {
                continue;
            }else if(caseRow <= col && caseCol <= row) {
                continue;
            }else {
                return false;
            }
        }

        return true;
    }

• 가로, 세로를 각각 오름차순으로 정렬하고 for문 돌면서 조합해서 가능한 최소 수를 찾으려고 했다. rowColCheck() 에서는 가로, 세로를 뒤집을 경우 된다면 통과한다.
• 테케 3개는 통과했는데 채점에서 실패. 완전 탐색까지 시킬필요 없는 문제이긴 하나 안된 원인 알고 싶은데 이유 못찾음..

3. 피드백

• 완전탐색이라고 해서 일단 조합해서 돌리려고 했는데 그럴 필요가 없었던 문제. 심지어 기본 테케는 통과해서 된건가 싶었는데 채점에선 실패. 이렇게 안짜도 되는건 알겠는데 완전 탐색이라면 이렇게 짤수도 있을 것 같아서.. 채찍피티한테도 이슈인 부분을 물어봤는데 정확히 파악을 못했다. 누가 제 코드의 이슈 부분을 파악한다면 알려주세요 ㅠㅠ
• 사고력을 더 키웁시다.. 휴..