[Python] 프로그래머스 Lv2_카펫

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

프로그래머스

 

 

• Leo는 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤음
• 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못함
• brown: 갈색 격자의 수
• yellow: 노란색 격자의 수
• 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return

제한사항

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

 

"""
입출력 예시)

brown = 10, yellow = 2 -> [4, 3]
brown = 8, yellow = 1 -> [3, 3]
brown = 24, yellow = 24 -> [8, 6]
"""

 

 

 

첫 번째 시도

 

## 의사코드 ##

# brown의 개수 + yellow의 개수 = 가로 * 세로
# -> 가로, 세로는 (brown의 개수 + yellow의 개수)의 약수

# 1) (brown의 개수 + yellow의 개수)의 약수 리스트를 구함

# 2) 약수 리스트를 오름차순 정렬

# 3) 세로는 3의 배수인 것을 이용해 세로 후보 리스트를 구함

# 4) 가로, 세로 후보 리스트를 생성해서 
# 세로 후보들 중에서 (brown의 개수 + yellow의 개수)를 나눴을 때의 몫이 자신보다 크거나 같은 경우가 가로이므로 
# 리스트.append((가로, 세로))

# 가로, 세로 후보 리스트 중 맨 첫 번째 튜플이 정답
# return [가로, 세로]

 

def solution(brown, yellow): 
    # brown의 개수 + yellow의 개수
    total = brown + yellow 
    # total의 약수 리스트
    divisor = [i for i in range(1, total+1) if total % i == 0] 
    # 약수 리스트 오름차순 정렬
    divisor.sort(reverse=True)
    # 세로 후보 리스트 (세로는 3의 배수)
    h_list = [d for d in divisor if d % 3 == 0]

    # 가로, 세로 후보 리스트
    wh_list = []
    # 세로 후보들 중에서 (brown의 개수 + yellow의 개수)를 나눴을 때의 몫이 자신보다 크거나 같은 경우가 가로 
    for h in h_list:
        if total // h >= h:
            w = total // h
            wh_list.append((w, h))

    return list(wh_list[0])

-> 추가 테스트 케이스 실패 (런타임 에러)

 

지난번에도 규칙 2가지 중에 한 가지를 못 찾아서 한 번에 통과하지 못했었는데 

이번에도 똑같은 규칙을 못 찾았다... 

 

뭔가 한가지 규칙이 더 있었던 건 기억이 나서 최대한 찾아보려고 계산해 봤는데 

• yellow의 개수 + 2 = 가로
• yellow의 개수 + 2 = 세로 

이렇게 까지는 알아냈는데 입출력 예시 3번 'brown = 24, yellow = 24 -> [8, 6]' 때문에 좀 헷갈렸다.

yellow 변수는 yellow의 개수를 의미하는 건데 yellow 격자의 크기라고 잘못 생각함...

 

그리고 다시 보니 첫 번째 시도에서 코드를 너무 비효율적으로 작성한 것 같다.

세로 후보 리스트, 가로와 세로 후보 리스트를 따로 리스트로 저장하지 않고 for문에서 조건문으로 한 번에 처리 가능했을 텐데 아쉽다..!

 

 

 

통과한 코드

 

## 의사코드 ##

# 규칙 1)
# brown의 개수 + yellow의 개수 = 가로 * 세로
# -> 가로, 세로는 (brown의 개수 + yellow의 개수)의 약수

# 규칙 2)
# (가로 - 2) * (세로 - 2) = yellow 
#   ex) brown = 24, yellow = 24 -> [8, 6]
#       -> yellow = 6 x 4

# size = brown + yellow

# size부터 1까지 역순으로 for문을 돌면서 가로 길이를 구함
#   if size % 가로 == 0:
#       세로 = size // 가로 # 세로는 size를 가로로 나눈 몫

      # if (가로-2) * (세로-2) == yellow:
      #     answer.append(x)
      #     answer.append(y)    

      # 가로가 세로와 같거나 커야하므로 answer를 오름차순 정렬해서 반환
      #return sorted(answer, reverse=True)

 

def solution(brown, yellow): 
    answer = []
    size = brown + yellow
    for w in range(size, 2, -1):
        if size % w == 0:
            h = size // w
            if (w-2) * (h-2) == yellow:
                answer.append(w)
                answer.append(h)
                return sorted(answer, reverse=True)

-> (가로 - 2) * (세로 - 2) = yellow 라는 규칙 추가

 

 

• (가로 - 2) * (세로 - 2) = yellow
  • brown과 yellow 격자 하나의 크기 = 1 x 1
  • ex) yellow = 2
    • -> yellow = 2 x 1
  • ex) brown = 24, yellow = 24 -> [8, 6]
    • -> yellow = 6 x 4

 

 

 

cf) 이전에 작성했던 코드

 

https://monzheld.tistory.com/52

[Python] 프로그래머스 Lv2_카펫