프로그래머스 문제 풀이 카펫

문제 URL 카펫

Contents

1. 문제 지문 파악하기
2. 구르미의 알고리즘 풀이

문제 지문 파악하기

이번에도 문제의 입력을 통해서, 문제를 파악해보도록 하겠습니다. 다음은, 첫 번째 입력입니다.

 

입력:
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에 대해서 약수는 다음과 같이 구할 수 있습니다.

 

1. x에 대해서, 1~n까지 다음을 반복합니다. ( 1<= x <= n)
2. n % x == 0 인지 판별합니다.
3. 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입니다. 이제 문제를 푸는데 필요한 모든 조각들은 모두 모았습니다. 이제 코드로써 직접 문제를 풀어보죠.

구르미의 알고리즘 풀이

"문제 지문 파악하기"를 토대로 세운 알고리즘을 순서대로 나열하면 다음과 같습니다.

 

1. red에 대해서 약수들을 구합니다.
2. x에 대해서 약수를 순회합니다.
   1. x의 짝 y를 구합니다.
   2. red의 둘레 2 * (x + y)와 brown - 4 가 만족하는지 확인합니다.
   3. 만족하면, y+2, x+2를 answer에 넣고 반환합니다.

조금 더, 프로그래밍적으로 풀어보면 다음과 같이 쓸 수 있습니다.

 

1. x에 대해서, 1 ~ red까지 다음을 반복합니다. (1 <= x <= red)
   1. x가 red의 약수인지 판별합니다.
   2. x가 약수라면, 짝 y를 구해줍니다.
   3. red의 둘레의 길이(2 * (x + y))가 brown -4 인지 판별합니다.
   4. 3번이 충족한다면, answer에 y+2, x+2를 넣어주고 반복을 멈춥니다.
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배 정도 연산의 수가 증가하긴 합니다. 하지만 알고리즘을 그대로 표현한다와 "완전 탐색" 파트를 잘 나타낸다는 점에서 더 높은 점수를 주고 싶네요.