[프로그래머스,Level 2] 카펫 (JAVA 구현)

- 첫 풀이

  이 문제를 읽고 처음 발견해낸 사실은 노란색 격자가 들어가기 위해선 무조건 세로의 길이가 3 이상이어야 한다는 것이다. 가로의 길이에 상관없이, 갈색 테두리인 두 개의 라인을 제거했을 때 노란색 격자가 존재하기 위해서는 3 이상이어야 했다.

 

  두 번째 알게 된 것은 갈색 격자 + 노란 격자 = 총 격자의 수이므로 총 격자의 수만큼 카펫을 만들 수 있는 경우는 총격자의 수의 약수들로 구할 수 있다는 사실이다. 입력 예제 3의 경우 갈색 격자 24개, 노란 격자 24개이므로 총격자의 수는 48이 되며, 만들 수 있는 경우의 수는 {1, 2, 3, 4, 6, 8, 12, 16, 24, 48}로 세로 1, 가로 48 /세로 2, 가로 24/ 세로 3 가로 16.....으로 총 5가지의 경우의 수가 발생한다.

 

  첫 번째 개념과 두 번째 개념을 결합하게 되면 세로가 3이상인 경우의 수를 고려하면 된다는 것까지 밖에 발견하지 못하고 제출을 하였더니 3개의 테스트 케이스에서 실패가 나왔다..

 

- 정답풀이

  위의 풀이를 이용하면 테스트 케이스 4, 6, 7에서 실패가 나오게 된다. 위 개념에서 간과한 것은 가능한 격자의 경우의 수들 중 노란색 격자를 주어진 값에 맞게 채울 수 있느냐를 판별하지 않았다는 것이다. 세로가 3이상인 격자를 만드는 경우의 수는 {3, 16}, {4, 12}, {6, 8}이 된다. 이 세 가지의 경우들 중 노란색 격자를 채우기 위한 경우의 수가 무엇인지 찾는 것이 이 문제가 원하는 답이다.

 

  {3, 16}은 세로 3에 가로가 16인 격자이다. 이때 모든 테두리는 갈색이므로 세로-2, 가로-2를 취한 후, 곱해주면 해당 영역이 노란색 격자로 채우는 경우이다. 1 * 14 = 14로 예제 3에서의 노란색 격자 24와는 다르므로 배제한다. {4. 12} 역시 2 * 10 = 20으로 24와 다르므로 배제하며, {6, 8}은 4 * 6 = 24이므로 예제 3에서 원하는 노란색 격자 24와 일치하므로 가로 8, 세로 6이 카펫의 최종 크기라 할 수 있다.

 

class Solution {
    public int[] solution(int brown, int yellow) {
        // 1. 0번 인덱스 : 가로, 1번 인덱스 : 세로
        int[] answer = new int[2];
        // 2. 총 격자의 수.
        int sum = brown + yellow;
        // 3. 약수를 구하기 위한 변수.
        int n;
        
        // 4. 세로는 3이상부터 총 격자 수의 제곱근까지 반복.
        for(int i = 3; i<=(int)Math.sqrt(sum);i++){
            // 5. 약수인 경우,
            if(sum % i == 0){
                n = sum / i;
                // 6. 노란색 격자의 수와 일치하는지 판단.
                if((i-2) * (n -2) == yellow){
                    answer[0] = n;
                    answer[1] = i;
                }
            }
        }
        
        return answer;
    }
}