[프로그래머스] 완전탐색 > 카펫 (자바)

프로그래머스 > 코딩테스트 연습 > 완전탐색 > 카펫 

 

문제 설명

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]

 

풀이

제한사항을 바탕으로 변수들이 만족해야 할 조건은 

1. brown + yellow = 넓이

2. 넓이 = answer[0] * answer[1] (가로 * 세로)

3. answer[0] >= answer[1]

4. answer[0] >=3 , answer[1] >= 3

5. (answer[0] - 2) * (answer[1] - 2) == yellow

 

아래 코드1은 이 모두를 조건이라고 생각해서 

area(넓이)의 약수를 구하는 것 부터 시작해서

조건을 모두 if문으로 달아주고 작성한 코드다.

 

▶ 코드1

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int area = brown + yellow;
        int num1;
        int num2;
        
        //조건
        // area = answer[0] + answer[1]; // brown + yellow
        // answer[0] >= 3;
        // answer[1] >= 3;
        
        //answer[]은 area의 약수!
        for(num1 = 3; num1 < area; num1++){
            for(num2 = 3; num2 < area; num2++){
                if(area % num1 == 0) {
                    if(num1 * num2 == area){
                        if(num1 >= num2) {
                            if((num1-2)*(num2-2) == yellow) {
                                answer[0] = num1;
                                answer[1] = num2;
                            }
                        }
                    }
                }
            }
            
        }
        
        
        return answer;
    }
}

 

조건문을 너무 많이 걸기도 했고 

for문을 area까지 돌려버려서 시간을 많이 뺐었다,

시간초과!!!!!

 

 

 

코드2는 num2 = area / num1이라는 코드를 추가해서 약수임을 (num1과 num2가 쌍으로)

표현하고 조건을 줄였더니 성공했다!

 

▶ 코드2

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int area = brown + yellow;
        int num1; //가로
        int num2; //세로

	for(num1 = 3; num1 < area; num1++){
            num2 = area / num1;
            if(num1 >= num2)
            if((num1-2)*(num2-2) == yellow) {
                answer[0] = num1;
                answer[1] = num2;
            }
        }

        return answer;
    }
}