[프로그래머스] 완전탐색 - 카펫 _ 자바Java

난이도: Level 2

 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]

---

 2. 알고리즘 by Yoon 

brown 기준으로 알고리즘을 생각했다.

 

1. 우선 모퉁이 네 곳을 지운다. num = brown - 4

    

2. brown을 아래와 같이 절반으로 나눈다. num = (brown -4) /2

   아래 예시같은 경우는 흰색 체크표시 된 타일이 num에 속한다고 생각하면 된다.

   이때 여기서 찾을 수 있는 흰트는 (흰색 세로 * 흰색 가로 = yellow 타일)이다.

 

3. 위 경우에서 num은 최종적으로 3이라는 값이 들어간다. 그럼 1부터 3까지 for문을 돌며 하나씩 탐색한다.

4. for문을 돌 때 index를 i라고 하면 i와 num-i 값을 곱해서 yellow 값과 동일한지 비교한다.

    그 이유는 2번에서 말한 이유와 동일하며, 이 과정은 yellow의 가로, 세로 값을 찾는 과정이다.

    4.1 동일하면 i와 num-i 중 더 큰 수를 width변수에, 더 작은 값을 height에 넣는다. (문제 조건)

    4.2 for문 break;

---

 3. 소스코드 

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        int num = (brown - 4)/2; 
        int width=0, height=0;
     
        for(int i = 1; i < num; i++){
            if((i * (num-i)) == yellow){
                if((i + 2) *(num - i + 2) == brown+yellow){
                    if(i > num-i){
                        width = i;
                        height = num-i;
                    }else{
                        width = num-i;
                        height = i;
                    }
                    answer[0] = width+2;
                    answer[1] = height+2;
                    break;
                }
                   
            }
        }
        
        return answer;
    }
}

---

 4. 느낀점 

풀리지 않던 부분에서 스터디를 하면서 스터디원의 도움으로 문제를 해결할 수 있었다.

알고리즘의 문제가 아닌 실수였는데 for문에서 첫 번째 if문의 조건문인 i * (num - i) 로 괄호 문제였다.. 나는 바보 . .

 

 

 

[Algo Rhythm🕺💃]

날짜: 2020.07.10