[프로그래머스] 카펫(python)

Programmers, 카펫

TL;DR

• 완전 탐색

문제 요약

1. 테두리가 갈색, 나머지 부분이 노란색으로 칠해져있는 카펫에 대해 노란색과 갈색의 각 격자의 크기의 수는 기억하고 있지만 전체 카펫의 개수는 기억하지 못한다.
2. 갈색과 노란색의 격자 개수를 통해 카펫의 가로, 세로 크기를 배열에 담아 반환한다.
3. 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 길다.

 

- 문제가 요구하는 카펫의 크기는 다양한 경우 중 최대한 정사각형에 가까운 크기를 반환해야 한다.

- '테두리가 갈색으로 이루어져 있다'가 문제 해결의 가장 큰 힌트이다.

    - 테두리가 갈색으로 이루어져 있기 때문에 노란색의 가로와 길이는 전체 카펫의 길이보다 2씩 작다.(왼쪽-오른쪽, 위-아래)

- 노란색의 크기가 될 수 있는 가로-세로 길이 조합에 가로와 길이에 2를 더했을 때 전체 카펫의 크기가 되는 경우가 정답이 된다.

입출력 형태

입출력 예시

 

예시 1 :: 갈색이 10개, 노란색이 2개로 이루어진 경우이다.

- 노란색이 될 수 있는 경우는 가로 2, 세로 1일때이며, 가로와 세로에 2를 더한 4와 3을 곱했을 때 전체 격자의 개수가 된다.

 

예시 2 :: 노란색이 1개인 경우 가로-길이가 1, 1인 경우이고 2를 더한 3, 3일 때 전체 크기가 된다.

 

예시 3 :: 노란색이 24가 되는 경우는 (6, 4), (8, 3), (12, 2), (24, 1)이 있다.

이 중 가로와 세로에 2를 더해서 모든 타일의 수인 48이 되는 경우는 (6, 4)에 2를 더한 (8, 6)이 된다.

풀이

import math

def solution(brown, yellow):
    # 테두리가 갈색 -> (노란색의 가로 + 2 * 노란색의 세로 * 2)가 크기가 되야함
    total = brown + yellow
    # 곱해서 노란색의 개수가 되는 경우의 수 파악
    yellow_comb = []
    for i in range(1, int(math.sqrt(yellow)) + 1):
        yellow_comb.append((yellow // i, i))
    # width와 height의 차이가 가장 적을 때부터 시작
    yellow_comb.sort(key=lambda x: x[1], reverse=True)

    for width, height in yellow_comb:
        if (width + 2) * (height + 2) == total:
            return [width + 2, height + 2]

 

앞서 언급한 바와 같이 두 수의 곱이 노란색의 개수가 되는 경우를 완전 탐색을 통해 확인한다.

- 이 때, 중복된 경우를 포함시키지 않게 하기 위해 yellow의 제곱근을 구한 범위까지, 즉, 노란색의 개수가 될 수 있는 절반까지 반복문을 진행한다.

- 이렇게 하면 두 수를 곱해서 노란색 타일의 수가 되는 모든 경우의 수 중 절반을 얻을 수 있다.

 

얻어낸 노란색의 수가 되는 리스트를 정렬하여 세로의 길이가 가장 작을 때로 정렬한다.

- 이 이유는 문제에서 요구하는 해답이 최대한 정사각형에 가까운 형태이기 때문이다.

- 또한 정사각형인 경우를 정답으로 하기 위해서이다.

 

노란색의 경우의 수에서 각각 2를 더해 모든 타일의 수가 되는 경우를 찾아 반환한다.