[프로그래머스] 카펫 - Java

문제 설명

 

코딩테스트 연습 - 카펫

 

접근 방법

해당 문제에서 요구하는 것은 갈색 격자의 수와 노란색 격자의 수가 주어졌을 때 이를 통해 카페의 가로, 세로 크기를 구하는 것입니다. 이때 문제 설명과 입출력 예시에 따르면 따르면 카펫 중앙에는 항상 노란색으로 칠해져 있고, 그 테두리에는 갈색으로 칠해져 있다는 사실을 확인할 수 있습니다.(문제에서 명확하게 설명되있다고 생각하지는 않지만) 이러한 조건을 토대로 답을 구하기 위해 다음과 같이 접근해보았습니다.

 

우선 가로 길이가 세로 길이와 같거나 커야하므로 주어진 노란색 격자의 가로 길이가 최대(주어진 숫자 그대로)일 때를 먼저 고려하여 그 주위를 갈색 격자가 모두 메울 수 있는지(사각형이 성립하는지)를 검사하도록 했습니다. 이때의 카펫의 가로 길이는 항상 노란색 격자의 +2(테두리 양 끝점 포함)인 값이며 세로의 길이는 갈색 격자의 수에서 앞서 구한 가로 길이들을 제한 후에 +2(테두리 양 끝점 포함)인 값이 됩니다.

 

        int total = brown + yellow, width = 0, height = 0;
        
        width = yellow + 2;
        height = ((brown - (width * 2)) / 2) + 2;
        
        if (height >= 3 && width * height == total) { // 조건 성립
            // ...
        }

 

이때 사각형의 높이가 3 이상이어야하는데, 이는 노란색 격자의 가로 길이가 최대일 때가 사각형의 높이가 최소 일때인데, 이때의 높이가 3이기 때문입니다. 최종적으로 구한 카펫의 가로 및 세로 길이를 서로 곱한 값이 갈색 격자와 노란색 격자의 수를 합친 값과 같다면 사각형이 성립할 것입니다. 만일 성립하지 않는다면 노란색 카펫 격자의 수의 약수를 내림차순 순서대로 노란색 격자의 가로 길이에 적용하여 위 작업을 반복해주면 됩니다.

 

 

전체 소스 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[] solution(int brown, int yellow) {
        int total = brown + yellow, width = 0, height = 0;
        List<Integer> divisorsOfYellow = getDivisors(yellow);

        for (Integer i : divisorsOfYellow) {
            width = i + 2;
            height = ((brown - (width * 2)) / 2) + 2;
            if (height < 3) {
                continue;
            }
            if (width * height == total) {
                break;
            }
        }

        return new int[]{width, height};
    }

    private List<Integer> getDivisors(int number) {
        List<Integer> divisors = new ArrayList<>();
        divisors.add(number);
        for (int i = number / 2; i > 0; i--) {
            if (number % i == 0) {
                divisors.add(i);
            }
        }
        
        return divisors;
    }
}

 

참고자료

• https://programmers.co.kr/learn/courses/30/lessons/42842