[프로그래머스] 카펫

문제 링크 >> https://programmers.co.kr/learn/courses/30/lessons/42842

 

 

📋 문제

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

 

 

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

 

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

 

 

👉 입출력

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

 

 

 

📝 풀이

❌ 첫 번째 풀이

def getDivisor(n):
  divisors = []
  
  for i in range(1, int(n**(1/2)) + 1):
    if n % i == 0:
      divisors.append([i, n//i])
      if i**2 != n:
        divisors.append([n//i, i])
  return list(filter(lambda x: x[0] >= x[1], sorted(divisors)))
  
def solution(brown, yellow):
    return getDivisor(brown+yellow)[0]

 

첫 번째 풀이는 약수를 이용하는 풀이였다.

brown + yellow로 총 격자의 수를 구하고 이 수의 약수 중 가로 길이가 세로 길이와 같거나 큰 것을 구하는 것이다.

그리고 구한 리스트 중 첫 번째 값을 출력하도록 했다.

 

뭔가 되지 않을까 했는데 아쉽게도 4, 6, 7번의 세 가지 테스트 케이스를 통과하지 못했다.

 

반례는 brown = 18, yellow = 6이 주어질 경우이다.

이 경우 내가 구한 답은 [6, 4]가 되는데 6x4의 타일에서는 문제에서 원하는 조건을 만족하지 못한다.

 

 

✔️ 두 번째 풀이

def getDivisor(n):
  divisors = []
  
  for i in range(1, int(n**(1/2)) + 1):
    if n % i == 0:
      divisors.append([i, n//i])
      if i**2 != n:
        divisors.append([n//i, i])
  return list(filter(lambda x: x[0] >= x[1], sorted(divisors)))
  
def solution(brown, yellow):
    arr = getDivisor(brown+yellow)
    for row, col in arr:
      if (row - 2) * (col - 2) == yellow:
        return [row, col]

 

테두리 1줄이 모두 갈색 격자이므로 노란색 격자가 1개일 때를 생각하면 아래와 같다.

 

 

노란색 격자를 감싼 형태가 되어야 하므로 row는 노란색 격자의 수보다 2개가 더 추가되어야 하고 column도 마찬가지로 2개가 더 추가되어야 한다.

따라서 row, column과 yellow 사이에는 (row - 2) * (column - 2) = yellow 라는 관계가 성립하게 된다.

 

이러한 변경 사항을 첫 번째 코드에 추가하니 원하는 답을 얻을 수 있었다.