문제 링크

문제 해결

초기 접근은

  • 너비(width)를 기준으로 1부터 최대길이까지 각 width에 맞는 height를 전부 탐색
  • 현재 조건에서 brown + yellow = 높이 * 너비를 만족하면 정답 리턴

이런식으로 구현하였다가, 일부 케이스에서 실패 및 시간초과가 나왔다. 직사각형을 만들기 위해 리스트를 append하는 부분에서 효율적이지 못한 코드였다.

문제의 조건을 다시 보고, 특정 w,h에서 yellow와 brown이 만족하는 조건에 초점을 맞춰서 다시 구현하였다.

기존 풀이방법의 width를 기준으로 height를 순회하는 방법을 사용하되, 조건을 각 w,h일때 입력으로 주어진 brown,yellow가 되는조건을 검사하여 해결하였다.

$$ \begin{align*} Brown = 2w + 2h - 4 \newline Yellow = (h-2) * (h-2) \end{align*} $$

코드

def solution(brown, yellow):
    answer = []
    # brown:  2w + 2h - 4
    # yellow: (w-2) * (h-2)
    for w in range(1, brown):
        for h in range(w+1):
            if (2*w + 2*h - 4) == brown and (w-2) * (h-2) == yellow:
                answer = [w,h]
                return answer

    return answer

실패한 코드

def solution(brown, yellow):
    answer = []

    # 최소 2 너비부터 시작
    for n in range(2, brown):
        carpet = []

        # n 크기의 사각형 윗 변(갈색)
        carpet.append([0] * n)

        height = 1 # 현재 높이

        # 높이는 너비보다 작거나 같아야 함
        while height < n:
            carpet.append([0] * n)

            # 현재 조건 체크
            if brown + yellow == len(carpet) * n:
                answer = [n, len(carpet)]
                return answer
                
            height += 1

    return answer