[고득점 Kit / 완전탐색] 카펫

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

 

이 문제는 작년쯤 풀었던 문제로 기억하는데, 이제야 해설을 하고자 한다.

 

이 문제는 다음과 같은 흐름으로 풀었다.

 

1. 전체 면적 계산(전체 타일의 개수는 brown + yellow)

2. 전체 타일 개수의 약수 쌍 구하기

3, 각 약수 쌍에서 테두리를 제외한 내부 영역의 면적이 노란 타일의 개수와 일치하는지 확인

 

 

def solution(brown, yellow):
    def divisor_pairs(n):
        pairs = []
        for i in range (1, n + 1):
            if n % i == 0 and i >= n // i:
                pair = (i, n //i)
                pairs.append(pair)
        return pairs
    
    square_count = brown + yellow
    divisor_list = []
    w = 0
    h = 0
    
    divisor_list = divisor_pairs(square_count)

    for i in range(len(divisor_list)):
        if (divisor_list[i][0] - 2) * (divisor_list[i][1] - 2) == yellow:
            w = divisor_list[i][0]
            h = divisor_list[i][1]

    answer = [w, h]
    
    return answer

 

 

def divisor_pairs(n):
    pairs = []
    for i in range (1, n + 1):
        if n % i == 0 and i >= n // i:
            pair = (i, n // i)
            pairs.append(pair)
    return pairs

 

 

• 이 함수는 숫자 n의 약수 쌍을 찾아 반환하는 역할을 한다.
• n % i == 0은 n이 i로 나누어떨어질 때만 약수라는 뜻이다.
• i >= n // i 조건은 (i, n // i) 쌍에서 가로 길이(i)가 세로 길이(n // i)보다 크거나 같을 때만 저장하도록 한다. 이렇게 하면 중복된 약수 쌍을 방지할 수 있다.
• 결과적으로 이 함수는 n의 가능한 가로와 세로 크기의 쌍을 반환한다.

 

square_count = brown + yellow

 

 

카펫의 전체 면적을 구한다. brown과 yellow를 합치면 전체 타일의 개수인 square_count가 된다. (즉, 이게 면적)

 

divisor_list = divisor_pairs(square_count)

for i in range(len(divisor_list)):
    if (divisor_list[i][0] - 2) * (divisor_list[i][1] - 2) == yellow:
        w = divisor_list[i][0]
        h = divisor_list[i][1]

 

 

• divisor_pairs(square_count)로 square_count의 가로, 세로 조합을 모두 찾는다. 예를 들어, square_count = 24라면 (6, 4), (8, 3) 등 여러 쌍이 나올 수 있다.
• for문을 사용하여 이 약수 쌍 중에서 카펫 내부의 노란 타일 크기에 맞는 쌍을 찾는다.
• (divisor_list[i][0] - 2) * (divisor_list[i][1] - 2) == yellow는 가로와 세로의 테두리(갈색 타일)를 제외한 부분이 노란 타일의 개수와 일치하는지 확인하는 조건이다.
  • 가로에서 양쪽 테두리 2칸(-2), 세로에서 위아래 테두리 2칸(-2)을 제외한 면적이 yellow와 같은지 확인한다.
• 조건에 맞는 가로(w), 세로(h) 값을 찾는다.

 

answer = [w, h]
return answer

 

가로와 세로 값을 [w, h] 형태로 리스트에 담아 반환한다.

 

 

테스트케이스로 로직이 어떻게 돌아가는지 확인해보자.

 

예를 들어, brown = 10, yellow = 2인 경우라 하자.

• 전체 타일의 수: square_count = 10 + 2 = 12
• divisor_pairs(12)를 호출하면 약수 쌍은 (4, 3)과 (6, 2)
• (4, 3)일 때, 테두리(갈색 타일)를 제외한 내부 면적은 (4 - 2) * (3 - 2) = 2 * 1 = 2, 이는 yellow와 일치한다.
• 따라서 가로는 4, 세로는 3이 된다.
• 최종적으로 [4, 3]을 반환하게 된다.