[프로그래머스] 카펫

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

프로그래머스

1. 문제 설명

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

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

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

---

2. 제한사항

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

---

3. 풀이

 

3.1. 로직

주어진 brown과 yellow를 사용해 가로, 세로를 구할 수 있음

> 가로 * 세로 = brown + yellow를 사용해보자

> 조건에 가로 길이는 세로 길이와 같거나 길다고 하니 넓이의 제곱근부터 시작하면 될 듯 !

 

3.2. 초기 코드

      

      

      

    
    

      <python />
    
# 초기 코드
def solution(brown, yellow):
    sum_width_height = brown // 2 + 2
    sum_brown_yellow = brown + yellow
    for width in range(int(sum_brown_yellow**(0.5)),sum_width_height):
        height = sum_width_height - width
        if width * height == sum_brown_yellow and width >= height:
            return [width, height]
# 0.25ms

 

문제 자체는 완전탐색 문제지만 그 범위를 넓이의 제곱근을 이용해 줄였다.

 

간단한 문제지만 개선할 점이 보인다

• 변수 정리
• range 범위 변경
• 조기 종료 조건

 

3.3. 1차 수정 : 변수 정리, range 범위 변경, 조기 종료 조건 추가

      

      

      

    
    

      <python />
    
# 1차 수정 : 가독성 개선 및 조건 정리
def solution(brown, yellow):
    total_area = brown + yellow
    sqrt_total_area = int(total_area**(0.5))
    if sqrt_total_area * 2 - 4 == brown:
        return [sqrt_total_area, sqrt_total_area]
    for height in range(3, sqrt_total_area + 1):
        if total_area % height == 0:
            width = total_area // height
            if (width + height) * 2 - 4 == brown:
                return [width, height]
# 0.15ms

 

range 범위가 확 줄었다. 대신 width가 아닌 height로 변경.

문제 조건에 brown이 8이상, yellow가 1이상 인 것으로 보아 3x3이 최소인 것 같다.

그래서 range도 아예 3부터 시작으로 최소한으로 줄임. 이런 섬세한 디테일이 좋다.

그리고 제곱근이 답일 경우를 조기 종료 조건으로 추가.

어차피 계산해야 하는 넓이의 제곱근을 변수지정(sqrt_total_area)하고 여러번 재사용.

 

이정도면 시간도 적절히 줄었고 로직도 맘에 든다. 가독성도 위보단 훨씬 좋은듯