[프로그래머스] 카펫 Java 풀이

문제 설명

 

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

 

입출력 예

brown	yellow	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

출처

※ 공지 - 2020년 2월 3일 테스트케이스가 추가되었습니다.
※ 공지 - 2020년 5월 11일 웹접근성을 고려하여 빨간색을 노란색으로 수정하였습니다.

 

 

처음 문제를 풀었을 때 이중 반복문으로 해결했는데, 다른 분들의 풀이를 보다 보니 반복문 하나로 보다 효율적으로 풀 수 있는 방법이 있었다.

 

처음 시도한 풀이의 접근 방식은 아래와 같다.

1. row를 3부터 2,000까지 탐색(row가 col보다 항상 같거나 작아야하는데, 2000 * 2000 == 4,000,000 > 2,005,000 )

2. col을 3부터 700,000까지 탐색(row가 3인 경우 3 * 700,000 == 2,100,000 > 2,005,000)

3. (row * 2) + (col * 2) - 4와 brown을 비교해본다. 

    3.1. (row * 2) + (col * 2) - 4와 brown보다 크면 break하고 row를 올려준다.

    3.2. (row * 2) + (col * 2) - 4와 brown이 같으면 brown은 만족하는 경우이므로 yellow 조건을 탐색한다.

        3.2.1. yellow 조건인 (row-2) * (col-2) == yellow이면 원하는 모든 조건을 모두 만족하므로 탐색을 종료한다. (전체 반복문 종료)

 

 

brown의 개수는 전체 테두리의 개수인데, 윗변과 아랫변, 좌변과 우변을 모두 더해주면 꼭지점 4개의 점이 중복되어 계산되므로 -4를 해주면 구할 수 있다. => (row * 2) + (col * 2) - 4

 

yellow의 개수는 테두리를 제외한 내부 영역이므로 전체 사각형에서 우변 col, 좌변 col, 윗변 row, 아랫변 row를 제외시키고 계산하면 되므로 다음과 같이 표현할 수 있다. => (row-2) * (col-2)

 

 

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        boolean found = false;

        // 최소 row col은 3*3부터 시작함
        // 최대 row는 2000(row^2 == 4000000 < 2005000)
        for(int row = 3; row <= 2000; row++){
            // 최대 col은 700000(2005000 < 3*700000), 최소 col은 row
            for(int col = row; col <= 700000; col++){
                // 적합한 row * col을 찾고, yellow도 만족하면 탐색 완료
                if(brown == (row * 2) + (col * 2) - 4
                  && (row-2) * (col-2) == yellow){
                    found = true;
                    answer[0] = col;
                    answer[1] = row;
                    break;
                }
                else if(brown < (row * 2) + (col * 2) - 4){
                    break;
                }
            }
            // row, col을 찾았으므로 탐색 중지
            if(found) {
                break;
            }
        }
        return answer;
    }
}

 

 

다른 분의 풀이는 이중 반복문을 돌리지 않고 row를 결정하면 brown 조건을 만족시킬 수 있는 col만 검사 대상으로 고려하는 로직으로 구성되어 있었다.

1. row를 3부터 brown + 4 / 2까지 탐색
(col이 row보다 크거나 같으므로 row+col == 2row이고, 이는 brown + 4보다 반드시 작거나 같아야함)

2. 현재 row에서 조건에 부합하는 col 계산

3. col이 row보다 작다면 continue

4. brown 조건을 만족할 때, yellow 개수를 세어보고 yellow와 비교해 같다면 탐색을 종료한다.

 

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        int height = 0;
        int width = 0;
        
        // brown 개수를 만족시킬 수 있는 범위에서 height 반복
        for(height = 3; height <= (brown + 4)/ 2; height++){
            // 현재 height에서 조건에 부합하는 width
            width = ((brown + 4) / 2) - height;
            // height가 width보다 클 수 없으므로 다음 height 탐색
            if(width < height){
                break;
            }
            // brown 조건에서 yellow 개수가 조건 yellow도 만족하면 탐색 종료
            int yellowCnt = (width - 2) * (height - 2);
            if(yellow == yellowCnt){
                break;
            }
        }
        
        answer[0] = width;
        answer[1] = height;
        
        return answer;
    }
}