[프로그래머스]카펫

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

프로그래머스

1. 문제

2. 풀이

카펫 가운데에 있는 노란색 격자가 위치할 수 있는 전체 카펫의 크기를 구하는 문제입니다. 처음에 문제를 이해하기가 쉽지 않았는데 우선 제일 먼저 떠올랐던 건

 

1) "brown + yellow => return 배열의 배열 요소끼리 곱한 값"

2) "brown(가로) >= yellow(세로)"

 

이 두 가지 였습니다. 하지만 저 두 가지 만으로는 도저히 문제를 풀 수 있는 해결방법이 떠오르지 않아서 문제에서 주어진 테스트케이스를 엑셀로 직접 구현해봤습니다.

 

보시면 그림과 같이 가운데에 노란색 격자가 위치하려면 가로와 세로가 최소한 3 이상이어야 합니다.

문제에서 요구하는 경우의 수를 찾으려면 카펫 사이즈의 경우의 수를 구해야 하는데 이 때 첫 번째 개념이 활용됩니다. 일단 'brown 격자 수 + yellow 격자 수' 의 약수를 구합니다.

 

예를 들어 brown = 10, yellow = 2 인 경우 12의 약수를 구합니다.

12의 약수를 순서쌍으로 나타내면 총 6가지가 있습니다.

 

(1, 12)

(2, 6)

(3, 4)

(4, 3)

(6, 2)

(12, 1)

 

이 경우의 수들 중에서 정답을 찾아내야 합니다.

여기서 두 번째 개념인 'brown(가로) >= yellow(세로)' 를 활용하는데 가로의 길이가 세로보다 길거나 같아야 하므로 경우의 수가 (4, 3), (6, 2), (12, 1)로 줄어듭니다. 그리고 가운데에 노란색 격자가 자리하려면 가로, 세로 길이가 모두 3이상이어야 하기 때문에 (6, 2), (12, 1)은 정답에서 제외됩니다. 

 

그렇게 되면 남은 (4, 3)이 최종 리턴값이 되는 것입니다.

참고로 해당 카펫이 입력으로 주어진 yellow의 개수만큼 노란색 격자가 가운데에 위치할 수 있는지 확인해야 하는데 이 경우 위의 그림의 사례를 통해 공식을 세울 수 있습니다. 가로, 세로의 길이가 모두 3이상이어야 하기 때문에 

 

yellow = (가로 - 2) * (세로 - 2)

 

이렇게 공식을 세워서 노란색 격자가 가운데에 위치할 수 있는지 확인합니다.

ex) (4 - 2) * (3 - 1) = 2 => 문제에서 주어진 가로 10, 세로 2 조건에 충족함

 

*코드

 
 
public class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int sum = brown + yellow;
 
        for (int i = 3; i < sum; i++) {
            int j = sum / i;
 
            if (sum % i == 0 && j >= 3) {
                int col = Math.max(i, j);         // 가로
                int row = Math.min(i, j);         // 세로
                int center = (col - 2) * (row - 2);
 
                if (center == yellow) {
                    answer[0] = col;
                    answer[1] = row;
                    return answer;
                }
            }
        }
        return answer;
    }
}