[프로그래머스/Programmers] 카펫 (Java - 완전탐색 - Lv2)

카펫 - 완전탐색

프로그래머스

---

⭐️ 코드

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];

        int tileSum = brown+yellow; // 전체 타일 개수
        int yellow_sqrt = (int)Math.sqrt(yellow);
        
        for(int i = yellow_sqrt; i>0; i--) {
            for (int j = yellow_sqrt; j <= brown; j++) {
                if (i * j == yellow) {
                    int x = j+2;
                    int y= i+2;
                    if ((x * y - yellow) == brown) {
                        answer[0] = x;
                        answer[1] = y;
                        return answer;
                    }
                }
            }
        }
        return answer;
    }
}

---

💡 문제 풀이

먼저 yellow는 항상 붙어있고 떨어져서 격자무늬를 만든다는 생각은 버리면 된다.

항상 brown에 둘러 쌓여 있다. 중간에 섞여서 출력되는 경우는 없다고 생각하고 풀어야 한다.

왜 그런지는 모르겠지만 나도 이걸로 조금 방황했었다..

 

완전 탐색의 한 방법인 이중 포문 방식으로 문제를 풀었다.

 

먼저 yellow 타일은 절대 떨어져 있지 않다는 가정 하에, brown 타일의 개수는 만족하는 yellow 타일의 가로/세로 + 2의 길이를 가진다.

따라서 yellow 타일의 개수가 24개라면, 가로 6, 세로 4의 사각형을 그리고, brown 타일은 가로 8, 세로 6의 길이를 가지게 된다. 

 

따라서 문제를 풀기 위해 먼저 yellow 타일의 제곱근을 구하게 되면 탐색하는 범위를 크게 줄일 수 있다. yellow 타일이 24개라고 가정했을 때 가장 큰 제곱근은 4 이기 때문에 4부터 하나씩 늘려가며 곱해서 yellow타일의 개수와 맞을 때 포문 아래 조건을 실행한다.

int yellow_sqrt = (int)Math.sqrt(yellow);

 

yellow의 제곱근부터 하나씩 내려가며 반복문을 수행하고

또 다른 반복문은 제곱근부터 하나씩 값을 올려가며 수행한다.

i와 j를 곱했을 때 그것이 주어진 yellow 값이라면 또 다른 if 조건을 수행한다.

두 번째 if 조건은 brown 타일의 개수를 구하면 되는데, 위에서 말했듯이 brown 타일은 yellow 타일의 가로/세로 + 2의 길이를 가지고 있기에, 그 내부는 yellow 타일로 채워져 있어 그만큼 값을 빼줘야 한다.

for(int i = yellow_sqrt; i>0; i--) {
    for (int j = yellow_sqrt; j <= brown; j++) {
        if (i * j == yellow) {
            int x = j+2;
            int y= i+2;
            if ((x * y - yellow) == brown) {
                answer[0] = x;
                answer[1] = y;
                return answer;
            }
        }
    }
}

모든 과정을 수행하고 값을 충족한다면 바로 return을 해줘도 상관없기 때문에 끝내줬다!

---

👀 후기

흠 뭔가 조금 이상한거 같지만.. 일단 풀었다..

만약 yellow 타일이 일정한 문양을 그렸다면 정말 풀기가 어려웠을 것 같다.