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

문제 설명

 

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

 

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

---

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

 

---

입출력 예

brown	yellow	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

---

 

풀이 코드

def get_candidate(tile):
    max_val = tile+1
    result = [] # [가로, 세로] 후보군
    for i in range(1, tile+1):
        if i > max_val:
            # 이미 후보군에 들어간 쌍이라면 더 후보군에 넣을 필요 없으므로 리턴.
            # 예를 들어, (a,b)가 후보군에 들어왔는데 (b,a)가 들어오려고 한다면 들어올 필요 없음.
            return result
        if tile % i == 0:
            # i가 tile 값의 약수라면
            pair = tile // i
            result.append([i, pair])
            max_val = pair
    return result
            
def solution(brown, yellow):
    tile = brown + yellow
    answer = []
    for can in get_candidate(tile):
        a, b = can
        # 타일 테두리 구하는 식.
        # 가로 * 2 + 세로 * 2 하면, 각 꼭지점이 2번씩 계산되었으므로 4를 빼주면 됨.
        tmp_brown = a*2 + b*2 - 4
        if tmp_brown == brown:
            # [a, b]에서 가로가 더 길다고 문제에서 주어졌으므로
            # [b, a]를 리턴하는 것이 옳음.
            answer.append(b)
            answer.append(a)
            break
    return answer

 

조금 돌아간 느낌은 있지만, 정상적으로 통과되는 코드이다.

문제 자체는 brute force(완전 탐색)과 조금의 수학이다.

코드 설명을 하자면, get_candidate는 타일의 총 개수를 파라미터로 받아, [가로, 세로]가 될 수 있는 후보군을 리턴 받는 함수이다.

자세한 내용은 주석으로 기재했으니 참고.

 

해당 후보군에서 테두리(brown)의 개수를 만족하는 후보를 찾아 리턴하면 된다.

직사각형의 변의 길이의 총 합은 가로 * 2 + 세로 * 2이다.

여기서는 타일의 개수를 따져야 하므로, 가로 * 2 + 세로 * 2로 계산하면 꼭지점 4개가 두 번씩 계산된다.

이를 고려하여 문제를 해결하면 된다.