[완전탐색/자바] 프로그래머스 lv2. 카펫

프로그래머스

 

문제 해석

위 문제는 brown 타일과 yellow 타일이 배치되는 간단한 규칙을 설명해주고, 각 타일의 개수가 주어졌을 떄, 어떤 모양으로 나올지를 탐색하여 그 모양의 가로와 세로 숫자를 반환하면 되는 문제였다.

 

이 문제의 경우에는 brown이 8 이상 5,000이하의 자연수, 그리고 yellow가 1이상 2백만 이하의 자연수이다. 완전탐색 로직을 생각해보면, yellow로 주어진 숫자를 1,2,3,4,5,...로 나눠서 딱 떨어지는 값에 대하여 brown개수가 일치하는지 볼 것이므로 완전탐색으로 계산하여도 시간복잡도가 O(N)에 그치기 때문에 실행 시간이 1000ms 이내로 들어옴은 확실하다.

 

따라서 이 문제는 완전탐색 로직으로 접근하였다.

 

풀이 로직

class Solution {
    public int[] solution(int brown, int yellow) {
        int width = 0;
        int height = 0;
        int[] answer = {};
        
        for (int i = 1; i <= yellow; i++) { 
            if (yellow % i != 0) { // 나머지가 있으면 pass
                continue;
            }
            width = yellow / i;
            height = i;
            if  (((width + height) * 2 + 4) == brown) {
                answer = new int[]{width+2,height+2};
                break;
            }
            if  (width < height) { // 세로가 가로보다 길어질 때부터는 연산 x
                break;
            }
            
        }
        
        return answer;
    }
}