[Algorithm: 완전탐색] 프로그래머스 <카펫>

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42842?language=java

프로그래머스

 

 

문제 설명

갈색과 노란색 격자의 개수가 주어진다. 카펫은 다음과 같은 구조이다.

• 가운데는 노란색 격자
• 가장자리는 갈색 격자(테두리 1줄)

노란색 영역을 갈색이 한 줄로 감싸는 형태이다. 이때 카펫의 전체 가로, 세로 길이를 구해야 한다.

 

조건은 다음과 같다.

• 가로 길이 ≥ 세로 길이
• 가운데 노란색 영역이 존재한다
• 갈색은 테두리 한 줄이다

 

---

 

처음 접근과 고민

노란색 영역을 다음과 같이 정의한다.

width × height = yellow

 

노란색 영역의 바깥에는 갈색 테두리가 한 줄씩 추가된다.

따라서 전체 카펫 크기는 다음과 같다.

(width + 2) × (height + 2)

 

전체 카펫의 격자 수는 brown + yellow이다. 따라서 다음 식을 만족해야 한다.

(width + 2) × (height + 2) = brown + yellow

 

이 식을 만족하는 (width, height) 조합을 찾으면 된다.

 

접근 방법: 완전 탐색

노란색 영역의 가로와 세로는 yellow의 약수 관계이다.

width × height = yellow 이 조건을 만족하는 모든 조합을 탐색하면 된다.

 

따라서 다음과 같은 방식으로 문제를 해결할 수 있다.

1. width를 1부터 yellow까지 순회한다.
2. yellow % width == 0이면 약수이다.
3. height = yellow / width 로 계산한다.
4. (width + 2) * (height + 2) 가 brown + yellow와 같으면 정답이다.

 

---

문제 풀이

노란색 약수 탐색

for (int width = 1; width <= yellow; width++)

 

노란색 영역의 가로 후보를 하나씩 탐색한다.

 

약수 확인

if (yellow % width == 0)

노란색 영역은 width × height = yellow를 만족해야 한다.

 

세로 길이 계산

int height = yellow / width;

노란색 영역의 세로 길이를 구한다.

 

카펫 조건 확인

(width + 2) * (height + 2) == brown + yellow

전체 카펫의 넓이가 갈색 + 노란색의 총 개수와 같다면 정답이다.

 

최종 코드

import java.util.*;

class Solution {
    public List<Integer> solution(int brown, int yellow) {
        List<Integer> answer = new ArrayList<>();

        for (int width = 1; width <= yellow; width++) {
            if (yellow % width == 0) {
                int height = yellow / width;
                
                if ((width + 2) * (height + 2) == brown + yellow) {
                    answer.add(height + 2);
                    answer.add(width + 2);
                    return answer;
                }
            }
        }
        
        
        return answer;
    }
}

 

 

 

 

---

 

 

기존 코드 개선하기

초기 코드에서는 width를 1부터 yellow까지 모두 탐색하는 방식으로 구현하였다.

for (int width = 1; width <= yellow; width++)

 

하지만 이 방식은 불필요하게 많은 반복을 수행한다는 단점이 있다.

 

노란색 영역의 가로와 세로는 다음 관계를 만족한다.

width × height = yellow

즉 yellow의 약수 관계이다. 약수는 항상 쌍으로 존재한다.

 

예를 들어 yellow = 24라면 약수 조합은 다음과 같다.

1 × 24
2 × 12
3 × 8
4 × 6

 

이 이후부터는

6 × 4
8 × 3
12 × 2
24 × 1

처럼 이미 확인한 조합이 반복된다.

 

이러한 약수의 특성 때문에 약수 탐색은 √N까지만 확인하면 충분하다.

1 ~ √yellow 이 범위에서 약수를 발견하면

그에 대응하는 다른 약수는 height = yellow / width로 자동으로 계산할 수 있다.

 

따라서 불필요한 반복을 제거하여 탐색 범위를 크게 줄일 수 있다.

 

개선된 코드

 

import java.util.*;

class Solution {
    public List<Integer> solution(int brown, int yellow) {

        List<Integer> answer = new ArrayList<>();

        for (int height = 1; height <= Math.sqrt(yellow); height++) {

            if (yellow % height == 0) {

                int width = yellow / height;

                if ((width + 2) * (height + 2) == brown + yellow) {
                    answer.add(width + 2);
                    answer.add(height + 2);
                    return answer;
                }
            }
        }

        return answer;
    }
}

 

개선된 부분

1. 탐색 범위 감소

기존 코드의 시간복잡도: O(yellow)

개선된 코드에서는 약수의 특성을 이용하여 O(√yellow)로 줄일 수 있다.

 

2. 약수 중복 탐색 제거

기존 방식은

2 × 12
12 × 2

 

위와 같이 같은 약수 조합을 두 번 탐색한다.

 

하지만 √yellow까지만 탐색하면

2 × 12

 

한 번만 확인하면 되므로 중복 연산을 제거할 수 있다.

 

 

---

 

 

정리

이 문제의 핵심은 다음 두 가지이다.

1. 노란색 영역은 yellow의 약수 관계이다.
2. 카펫 전체 크기는 (width + 2) × (height + 2)이다.

따라서 yellow의 약수 조합을 탐색하면서 brown 조건을 만족하는 경우를 찾으면 된다.

 

또한 약수 탐색을 √yellow까지만 수행하도록 개선하면 성능을 크게 향상시킬 수 있다.