Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
- 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
- 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
- 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
입출력 예
| brown | yellow | return |
| 10 | 2 | [4, 3] |
| 8 | 1 | [3, 3] |
| 24 | 24 | [8, 6] |
나의 풀이
def solution(brown, yellow):
yellow_set = []
for i in range(1,int(yellow**0.5)+1) :
if yellow % i == 0 :
yellow_set.append((yellow//i, i))
for yellow_width, yellow_height in yellow_set :
width = yellow_width + 2
height = yellow_height + 2
if width*2 + (height-2)*2 == brown :
return [width, height]
step 1
- 노란색 타일의 개수가 주어졌으므로, a x b = 노란색 타일 개수 의 형태를 만든다.
- 모든 약수는 항상 짝을 이루고, 그 짝끼리 곱한 값이 해당 숫자가 된다. (따라서 제곱근까지만 확인한다면, 그 이후는 이미 앞에서 짝을 이룬 중복된 값)
- ex) 노란색 타일이 24개 : (1,24) (2,12) (3,8) (4,6)
- 따라서 노란색 타일 개수의 제곱근까지 반복문을 돌며, yellow 가 i로 나눠진다면,
- 몫과 i를 가로,세로의 길이가 될 수 있는 후보 집합에 추가하였다.
- 몫이 더 크므로 가로, i는 제곱근 이전의 값이므로 항상 가로보다 작거나 같은 세로가 된다.
step 2
- 노랑색의 가로, 세로 길이가 될 수 있는 후보 집합의 원소들을 하나씩 돌면서,
- 해당 값으로 타일의 전체 가로, 세로 길이를 구한다.
- 타일 전체 가로 = 노란 타일 + 2
- 타일 전체 세로 = 노란 타일 + 2
- 따라서 타일가로 * 2 + (타일세로-2)*2 가 갈색의 타일 개수와 일치하다면,
- 해당 [타일 전체 가로, 타일 전체 세로] 값을 리턴한다.
보완된 풀이
def solution(brown, yellow):
for i in range(1,int(yellow**0.5)+1) :
if yellow % i == 0 :
if ((yellow//i + i) * 2 == brown - 4) :
return [yellow//i + 2, i+2]굳이 set 을 이용하지 않고 조건문 두개로 한번에 리턴하는 방법이다!
댓글