프로그래머스 문제 풀이 카펫
문제 URL 카펫
Contents
- 문제 지문 파악하기
- 구르미의 알고리즘 풀이
문제 지문 파악하기
이번에도 문제의 입력을 통해서, 문제를 파악해보도록 하겠습니다. 다음은, 첫 번째 입력입니다.
입력:
brown = 10
red = 2
이 때, 만들 수 있는 직사각형은 문제의 그림처럼 빨간색 타일이 2x1 형태로 잡혀 있는 형태입니다.
| B | B | B | B |
| B | R | R | B |
| B | B | B | B |
따라서, [4, 3] 형태를 반환해야 합니다. 이번엔 두 번째 입력을 살펴봅시다.
입력:
brown = 8
red = 1
이번엔 다음과 같이 빨간색 타일이 1x1 형태로 잡혀있을 때, 가장 큰 가로, 세로인 3x3인 사각형이 됩니다.
| B | B | B |
| B | R | B |
| B | B | B |
이번엔 세 번째 예제입니다.
입력:
brown = 24
red = 24
이 때, 빨간색 타일이 6x4 형태로 가운데 존재해야 가장 큰 가로, 세로인 8x6인 사각형이 됩니다.
| B | B | B | B | B | B | B | B |
| B | R | R | R | R | R | R | B |
| B | R | R | R | R | R | R | B |
| B | R | R | R | R | R | R | B |
| B | R | R | R | R | R | R | B |
| B | B | B | B | B | B | B | B |
세가지 예제를 주의 깊게 살펴봅시면, 빨간색 타일, 갈색 타일에 대해서, 다음 수식을 만족해야 가장 큰 직사각형이 만들어집니다.
(빨간색 타일로 이루어진 사각형의 둘레 == 갈색 타일 개수 - 4)
한 번 손으로 이 수식이 모든 상황에 들어 맞는지 풀어보세요. 이제 문제는 간단해집니다. 빨간색 타일로 만들 수 있는 직사각형을 만들고, 그 둘레의 길이가 갈색 타일의 개수보다 4 작은지 확인해서, 가장 큰 가로, 세로를 구하면 됩니다. 어떻게 풀 수 있을까요? 세번째 예제로 문제를 살펴봅시다.
입력:
brown = 24
red = 24
먼저 우리는 red에 대해서, 모든 약수를 구합니다.
약수 = [1, 2, 3, 4, 6, 8, 12, 24]
그래서, 이 약수들과 그 짝에 대해서 위의 수식이 맞는지 확인합니다. 먼저 약수 1일때 상황입니다.
brown = 24
x = 1
y = 24
2 * (x + y) = 50 != brown - 4 = 20
수식이 맞을때까지 계속 반복합니다.
brown = 24
x = 2
y = 12
2 * (x + y) = 28 != brown - 4 = 20
x = 3
y = 8
2 * (x + y) = 22 != brown - 4 = 20
x = 4
y = 6
2 * (x + y) = 20 == brown - 4 = 20
즉, x=4, y=6일 때, 빨간색 타일을 가운데로 하는 최대 사각형을 구할 수 있습니다. 이 때, 사각형의 가로, 세로 길이는 x+2, y+2한 값입니다. 여기서 중요한 것은, 무조건, 첫번째 원소가 커야 하는 것입니다. 즉, 다음을 반환하면 됩니다.
answer = [ 8, 6 ] // [ y+2, x+2 ]
이제 중요한 것은 약수를 어떻게 구하느냐입니다. 일반적으로 숫자 n에 대해서 약수는 다음과 같이 구할 수 있습니다.
- x에 대해서, 1~n까지 다음을 반복합니다. ( 1<= x <= n)
- n % x == 0 인지 판별합니다.
- 2번을 충족하는 모든 x들을 반환합니다.
코드로 표현하면 다음과 같습니다.
def get_measure(n):
return [ x for in range(1, n+1) if n % x ==0 ]
숫자 n, 약수 x에 대해서, x의 짝 y는 다음 수식을 이용하여 풀 수 있습니다.
y = n // x
즉 숫자 n을 x로 나눈 몫이 바로 y입니다. 이제 문제를 푸는데 필요한 모든 조각들은 모두 모았습니다. 이제 코드로써 직접 문제를 풀어보죠.
구르미의 알고리즘 풀이
"문제 지문 파악하기"를 토대로 세운 알고리즘을 순서대로 나열하면 다음과 같습니다.
- red에 대해서 약수들을 구합니다.
- x에 대해서 약수를 순회합니다.
- x의 짝 y를 구합니다.
- red의 둘레 2 * (x + y)와 brown - 4 가 만족하는지 확인합니다.
- 만족하면, y+2, x+2를 answer에 넣고 반환합니다.
조금 더, 프로그래밍적으로 풀어보면 다음과 같이 쓸 수 있습니다.
- x에 대해서, 1 ~ red까지 다음을 반복합니다. (1 <= x <= red)
- x가 red의 약수인지 판별합니다.
- x가 약수라면, 짝 y를 구해줍니다.
- red의 둘레의 길이(2 * (x + y))가 brown -4 인지 판별합니다.
- 3번이 충족한다면, answer에 y+2, x+2를 넣어주고 반복을 멈춥니다.
- 이렇게 초기화된 answer를 반환합니다.
다음을 코드로 나타내면 다음과 같습니다. 먼저 PYTHON 코드입니다.
PYTHON 코드
def solution(brown, red):
answer = []
# 1. 1 ~ red 까지 다음을 반복합니다.
for x in range(1, red+1):
# 1. 약수인지 판별합니다. 아니라면, 넘어갑니다.
if red % x != 0:
continue
# 2. 약수 x의 짝 y를 구해줍니다.
y = red // x
# 3. red 둘레 == brown - 4 일 때, [y + 2, x + 2]를 반환합니다.
if 2 * (x + y) == brown - 4:
answer = [y + 2, x + 2]
break
return answer
다음은 CPP 코드입니다. 알고리즘은 동일합니다.
CPP 코드
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int brown, int red) {
vector<int> answer;
for (int x=1; x<=red; x++) {
if (red % x != 0) {
continue;
}
int y = red / x;
if (2 * (x + y) == brown - 4) {
answer = { y + 2, x + 2 };
break;
}
}
return answer;
}
또한, "모든 약수를 순회한다"라는 것을 직접적으로 코드로 표현할 수도 있습니다. 다음처럼 말이죠.
PYTHON 코드
def solution(brown, red):
answer = []
candidates = [ (x, red // x) for x in range(1, red + 1) if red % x == 0 ]
for (x, y) in candidates:
if 2 * (x + y) == brown - 4:
answer = [y + 2, x + 2]
break
return answer
근데 위의 코드의 경우, 2배 정도 연산의 수가 증가하긴 합니다. 하지만 알고리즘을 그대로 표현한다와 "완전 탐색" 파트를 잘 나타낸다는 점에서 더 높은 점수를 주고 싶네요.