프로그래머스의 카펫 문제를 함께 풀어보도록 하겠습니다.
문제
Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
- 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
- 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
- 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
예제
입력: brown = 10, yellow = 2
출력: [4, 3]입력: brown = 8, yellow = 1
출력: [3, 3]입력: brown = 24, yellow = 24
출력: [8, 6]풀이 1
문제에서 주어진 그림을 보면 카펫은 두 개 사각형으로 이루어졌다는 것을 알 수 있는데요. 첫 번째 사각형은 두께가 1인 갈색으로 이루어진 큰 사각형이고, 두 번째 사각형은 그 안에 있는 노란색으로 이루어진 작은 사격형입니다.
카펫은 갈색 격자와 노란색 격자로 이루어져 있으므로 갈색 격자의 개수와 노란색 격자의 개수를 합치면 카펫에 있는 격자의 총 개수가 되는데요. 그리고 이 카펫에 있는 총 격자의 개수는 카펫의 너비와 높이를 곱한 값, 즉 카펫의 넓이와 일치할 것입니다.
문제에서 주어진 첫 번째 예제로 생각을 해보면, 10개의 갈색 격자와 2개의 노란색 격자로 이루어진 카펫이므로 총 격자의 개수는 12개입니다. 카펫의 너비는 4이고, 높이는 3이므로 4 x 3 = 12가 되어 총 격자의 개수와 일치한다는 것을 알 수 있습니다.
하지만 이러한 조건을 만족하는 카펫의 너비와 높이가 여러 쌍이 나올 수 있습니다. 따라서 우리는 이 중에서 한 쌍을 찾기 위해서 추가적인 조건을 필요하다는 것을 알 수 있는데요.
갈색 격자로 둘러쌓여 있는 노란색 격자의 개수는 어떻게 구할 수 있을까요?
카펫의 너비에서 2를 뺀 값과 카펫의 높이에서 2를 뺀 값을 곱하면 노란색 부분의 넓이를 구할 수 있을 것이고, 이 것이 입력으로 주어진 yellow, 즉 노란색 격자의 개수와 일치해야할 것입니다.
정리를 해보면 다음 2개의 수식을 만족하는 카펫의 너비와 높이의 쌍을 구해야하는 문제라는 것을 알 수 있습니다.
큰 사각형의 넓이 (카펫의 넓이)
= 갈색 격자의 개수 + 노란색 격자의 개수
= 카펫의 너비 x 카펫의 높이
작은 사각형의 넓이
= 노란색 격자의 개수
= (카펫의 너비 - 2) x (카펫의 높이 - 2)제한 사항을 보면 펫의 너비가 높이보다 길거나 같고, 노란색 격자의 수가 최소 1이라고 합니다. 그러므로 우리는 카펫이 높이를 3부터 시작해서 총 격자의 개수의 제곱근까지 증가시키면서 카펫의 가로 길이를 찾을 수 있을 것입니다. 카펫의 높이를 3부터 증가시키는 이유는 노란색 격자 부분은 반드시 갈색 격자로 둘러쌓여 있어야 하기 때문에 카펫의 높이가 최소 3이 될 것이기 때문입니다.
그럼 파이썬으로 이 알고리즘을 구현해볼까요?
def solution(brown, yellow):
area = brown + yellow
for height in range(3, int(area**0.5) + 1):
if area % height == 0:
width = area // height
if (width - 2) * (height - 2) == yellow:
return [width, height]같은 코드를 자바스크립트로 구현하면 다음과 같습니다.
function solution(brown, yellow) {
const area = brown + yellow;
for (let height = 3; height <= Math.sqrt(area); height++) {
if (area % height === 0) {
const width = area / height;
if ((width - 2) * (height - 2) === yellow) {
return [width, height];
}
}
}
}카펫을 이루고 있는 격자의 수를 n이라고 했을 때 이 풀이의 시간 복잡도는 O(sqrt(n))이 됩니다.
공간 복잡도는 정해진 개수의 변수 외에는 추가 메모리를 사용하지 않기 때문에 O(1)입니다.
풀이 2
이전 풀이에서는 카펫의 넓이와 그 안에 들어있는 노란색 사각형의 넓이를 이용하여 문제를 풀었는데요. 이번에는 카펫의 둘레를 이용해서 문제를 풀어보면 어덜까요?
갈색 격자의 개수에 4를 더하면 카펫의 둘레를 구할 수 있습니다. 4를 더해야하는 이유는 4개의 모서리에 있는 격자는 2개의 면에 닿아있기 때문입니다. 예를 들어, 첫 번째 예제에서 주어진 카펫의 경우, 갈색 격자의 개수는 10인데, 둘레는 14라는 것을 알 수 있습니다.
카펫의 너비와 높이의 합은 카펫의 둘레의 절반과 같은데요. 이 사실을 이용하면 높이를 알면 항상 너비를 구할 수 있죠. 둘레에서 높이만 빼면 되니까요.
우리는 카펫이 높이를 3부터 둘레의 반에 반까지 증가시키면서 카펫의 너비를 찾을 수 있을 것입니다. 카펫의 높이와 너비를 곱한 값이 갈색 격자의 개수와 노란색 격자의 개수의 합과 동일해야할 것입니다.
이 알고리즘을 파이썬으로 구현해보겠습니다.
def solution(brown, yellow):
half_peri = (brown + 4) // 2
# 또는 half_peri = brown // 2 + 2
for height in range(3, half_peri // 2 + 1):
width = half_peri - height
if width * height == brown + yellow:
return [width, height]같은 코드를 자바스크립트로 구현하면 다음과 같습니다.
function solution(brown, yellow) {
const halfPeri = (brown + 4) / 2;
for (let height = 3; height < halfPeri; height++) {
const width = halfPeri - height;
if (width * height === brown + yellow) {
return [width, height];
}
}
}카펫의 둘레를 p이라고 했을 때 이 풀이의 시간 복잡도는 O(0.25p) = O(p)가 됩니다.
공간 복잡도는 정해진 개수의 변수 외에는 추가 메모리를 사용하지 않기 때문에 O(1)입니다.
풀이 3
이전 두 개의 풀이 모두 카펫의 너비와 높이를 선형 탐색으로 찾고 있는데요. 만약에 이분 탐색(Binary Search)으로 찾을 수 있다면 성능을 향상시킬 수 있을 것입니다.
이분 탐색을 수행하려면 검색 범위의 중간에 있는 높이를 기준으로 언제 앞 부분을 탐색하고 언제 뒷 부분을 탐색할지를 판단할 수 있어야 하는데요. 카펫의 높이와 너비의 곱을 카펫의 넓이와 비교해보면 됩니다.
- 카펫의 높이와 너비의 곱이 카펫의 넓이보다 작다면, 카펫의 높이가 너무 작다는 뜻입니다. 따라서, 좌측 절반을 탐색 범위에서 제외시켜야 합니다.
- 카펫의 높이와 너비의 곱이 카펫의 넓이보다 크다면, 카펫의 높이가 너무 크다는 뜻입니다. 따라서, 우측 절반을 탐색 범위에서 제외시켜야 합니다.
- 카펫의 높이와 너비의 곱이 카펫의 넓이와 같다면, 원하는 카펫의 높이를 찾아다는 뜻입니다. 따라서, 탐색을 종료할 수 있습니다.
카펫의 높이와 너비의 곱이 카펫의 넓이보다 작을 때, 왜 카펫의 높이를 키워야하는지 햇갈리실 수 있을 것 같은데요. 문제에서 주어진 세 번째 예제로 같이 생각을 해볼까요?
입력: brown = 24, yellow = 24
출력: [8, 6]갈색 격자의 개수가 24이고, 노란색 격자의 개수 24이므로 이 카펫의 넓이는 48입니다. 그리고 카펫의 둘레는 갈색 격자의 개수에 4를 더하면 28이 됩니다. 카펫의 높이와 너비의 합은 카펫의 둘레의 절반인 14가 되야 하죠.
| 높이 | 너비 | 넓이 |
|---|---|---|
| 3 | 14 - 3 = 11 | 3 x 11 = 33 |
| 4 | 14 - 4 = 10 | 4 x 10 = 40 |
| 5 | 14 - 5 = 9 | 5 x 9 = 45 |
| 6 | 14 - 6 = 8 | 6 x 8 = 48 |
| 7 | 14 - 7 = 7 | 7 x 7 = 49 |
보시는 것처럼 카펫의 높이가 커질 수록 카펫의 넓이가 커진다는 것을 볼 수 있습니다. 카펫의 모양이 정사각형에 가까워질 수록 카펫의 넓이가 넓어지는 것이지요.
지금까지 설명드린 이분 탐색 알고리즘을 파이썬으로 구현해보겠습니다.
def solution(brown, yellow):
half_peri = (brown + 4) // 2
low, high = 3, half_peri // 2
while low <= high:
height = (low + high) // 2
width = half_peri - height
if width * height < brown + yellow:
low = height + 1
elif width * height > brown + yellow:
high = height - 1
else:
return [width, height]같은 코드를 자바스크립트로도 구현해보았습니다.
function solution(brown, yellow) {
const halfPeri = Math.floor((brown + 4) / 2);
let low = 3;
let high = Math.floor(halfPeri / 2);
while (low <= high) {
let height = Math.floor((low + high) / 2);
let width = halfPeri - height;
if (width * height > brown + yellow) {
high = height - 1;
} else if (width * height < brown + yellow) {
low = height + 1;
} else {
return [width, height];
}
}
}카펫의 둘레를 p이라고 했을 때 이 풀이의 시간 복잡도는 O(log p)가 됩니다.
공간 복잡도는 p와 상관 관계없이 항상 일정한 메모리를 소모하므로 O(1)이 되겠습니다.