[JAVA] 프로그래머스 : 카펫 (코딩테스트 고득점 kit > 완전탐색)

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

코딩테스트 연습 - 카펫

첫 번째 풀이

카펫의 중앙 부분의 가로, 세로 길이를 이용하여 완전 탐색을 이용해 문제를 풀었음

 

해결 방안

1. 문제에 주어진 input으로 테두리(갈색) 갯수와 중앙(노란색) 갯수를 알 수 있고 이 것을 통해 카페의 전체 total 갯수를 알 수 있다고 생각함 

2. 전체 갯수는 (yellow 부분의 가로+2) * (yellow 부분의 세로+2)와 같다고 생각함
=> 테두리(갈색)가 한 줄 이므로 전체 가로 길이 = 왼쪽, 오른쪽 테두리(yellow 부분의 가로+2), 전체 세로 길이 = 위, 아래 테두리(yellow 부분의 세로+2)

3. yellow 갯수도 (yellow 부분의 가로) * (yellow 부분의 세로) 와 같음

4. 두 가지 조건(2,3)에 맞는 yellow의 가로,세로 길이를 찾기 위해 이중 반복문을 이용하여 가로 길이에 따른 세로 길이를 +1씩 해주면서 완전 탐색함

5. 답을 찾는데 걸리는 시간을 줄이기 위해 세로 길이를 늘려주면서 (카펫의 가로 길이 >= 세로 길이) 조건을 만족하지 않을때 break 함

 

코드

// 카펫
// 중앙은 노란색, 테두리 1줄이 갈색인 카펫
// 카펫 가로길이 >= 세로길이
class Solution {
    public int[] solution(int brown, int yellow) {
        // 카펫 가로, 세로 크기
        int[] answer = new int[2];
        
        int total = brown + yellow;
        
        // yellow
        int yWidth = 0;
        int yHeight = 0;
        
        // 전체 갯수 = (옐로 부분 가로 + 2) * (옐로 부분 세로 + 2)
        while(total != (yWidth+2) * (yHeight+2)){
            yWidth++;
            yHeight = 0;

            // yellow 갯수 = 옐로 부분 가로 * 옐로 부분 세로 
            while(yellow != yWidth * yHeight){
            	yHeight++ ;              
                // 세로 길이가 가로길이보다 길면 break
                if(yHeight >= yWidth) {
                	break;                	
                }
            }   
        }
        
        // yellow의 약수들 다 구한다음
        answer[0] = 2 + yWidth;
        answer[1] = 2 + yHeight;

        return answer;
    }
}

 

두 번째 풀이

 

해결 방안

1. 전체 크기를 total에 저장해주고 x(가로의 크기)를 total부터 1까지 줄여나가는 반복문을 이용하였다.
이때 total이 x(가로)로 나눠지면 y(세로)를 구해주고 구해진 x(가로), y(세로)를 이용하여 brown이 될 부분을 구해서 실제 brown 값과 비교해서 값이 같으면 그때 x(가로), y(세로) 값이 정답이므로 break해준다.

코드

// 카펫
// 중앙 노란색 테두리 1줄은 갈색
// 노란색 갈색 갯수 기억
// 카펫의 가로 길이는 세로 길이와 같거나 세로 길이보다 김
class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = {0,0};
        int x = 0; // 가로
        int y = 0; // 세로
        int total = brown + yellow;
        
        int tempBrown;
        for(int i=total; i>0; i--){
            x = i;
            
            // total이 x로 나눠지면 y 구함
            if(total % x == 0){
                y = total/x;
                
                tempBrown = (2*x + 2*y) -4;
                if(tempBrown == brown)
                    break;
            }
            else{
                continue;
            }
        }
        
        answer[0] = x;
        answer[1] = y;
        return answer;
    }
}