출처ㅣ Programmers 코딩테스트 고득점 Kit

Brute-force: 카펫 [Lv2]

문제 설명

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]

&nbsp

<span style="color:#48AB7E">Solution</spsn>

내 풀이


def solution(brown, yellow):
    answer = []
    yellow_area = set()
    for i in range(1, yellow // 2 + 2):
        if yellow % i == 0:
            a, b = i, yellow // i
            tmp = tuple(sorted([a, b]))
            yellow_area.add(tmp)

    yellow_area = list(yellow_area)
    for aliquots in yellow_area:
        len_col = aliquots[0] + 2
        len_row = aliquots[1] + 2
        if len_col * len_row - yellow == brown:
            answer = [len_row, len_col]
            break
    return answer

yellow를 1부터 yellow // 2 + 1까지의 수로 나눠보면서 나머지가 0이 되면 나눈 수와 값을 오름차순 순서로 튜플로 만들어 yellow_area에 추가한다. 즉, yellow의 약수들을 저장하는 것이다. 그 다음 for문에서 yellow_area에 저장된 값들을 가져와서 이 값들로 카펫 가운데의 영역을 지정한다면, 그 때 생기는 borwn의 영역이 주어진 값과 동일한지 비교한다.

결과

Best Code

def solution(brown, yellow):
    for i in range(1, int(yellow**(1/2))+1):
        if yellow % i == 0:
            if 2*(i + yellow//i) == brown-4:
                return [yellow//i+2, i+2]

원리 자체는 내가 만든 코드와 비슷하다. 하지만 내 코드에 비해서 더 효율적이고 길이가 압축적이다. 내가 for문에서 범위를 yellow // 2 + 2까지 했던 것을 이 코드에서는 yellow ** (1/2) + 1까지이다. 그리고 내가 (yellow 영역의 가로길이 + 2) * (yellow 영역의 세로길이 + 2) - yellow == brown 이라고 만든 것을 이 코드는 2*(i + yellow // i ) == brown - 4로 검증했다.

결과

내 코드에 비해 결과 속도도 확실히 빠르다.