문제 설명
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] |
풀이
from math import sqrt
def get_one_row_include_yellow(num_of_row_yellow):
return num_of_row_yellow + 2
def get_row_include_yellow(yellow, div):
return get_one_row_include_yellow(yellow // div) * div
def get_total_grid(yellow, div):
row_include_yellow = get_row_include_yellow(yellow, div)
return row_include_yellow + (get_one_row_include_yellow(yellow // div) * 2)
def is_saw_carpet(yellow, div, brown):
if get_total_grid(yellow, div) - yellow != brown:
return False
return True
def get_carpet_row_col(yellow, div):
row = get_one_row_include_yellow(yellow // div)
col = div + 2
return [row, col]
def solution(brown, yellow):
if is_saw_carpet(yellow, 1, brown):
return get_carpet_row_col(yellow, 1)
for div in range(2, int(sqrt(yellow)) + 1):
if not (yellow % div) and (yellow // div) >= div:
if is_saw_carpet(yellow, div, brown):
return get_carpet_row_col(yellow, div)
if (yellow // div) != div and div >= (yellow // div):
if is_saw_carpet(yellow, (yellow // div)):
return get_carpet_row_col(yellow, (yellow // div))해결 과정
노란색을 포함하고 있는 가로 한 줄의 격자 개수 구하기
전체 타일 격자 개수를 구해야 한다. 또한, 노란색이 포함된 가로줄은 총 몇 줄인지도 알아야 하기 때문에 먼저 노란색을 포함하고 있는 가로 한 줄에는 몇 개의 격자가 필요한지 구하기로 했다.
def get_one_row_include_yellow(num_of_row_yellow):
return num_of_row_yellow + 2노란색을 포함하고 있는 가로 한 줄은 (한 줄에 있느 노란색 타일 수) + 2다. 왜냐하면 양끝의 노란색은 갈색에 의해 막히기 때문이다.
노란색이 있는 가로줄의 격자 개수 구하기
def get_row_include_yellow(yellow, div):
return get_one_row_include_yellow(yellow // div) * div이 경우는 위에서 구한 격자 개수에다가 노란색이 연속적으로 세로로 몇 줄이 있는지만 알면 구할 수 있다. 이 함수에서는 div가 노란색 격자가 세로로 몇 줄 연속되어 있는지를 나타낸다.
전체 격자 개수 구하기
def get_total_grid(yellow, div):
row_include_yellow = get_row_include_yellow(yellow, div)
return row_include_yellow + (get_one_row_include_yellow(yellow // div) * 2)전체 격자 수는 (노란색이 포함되어 있는 가로줄의 격자 수) + (노란색이 포함되어 있는 가로 한 줄의 격자 수 * 2)라는 공식을 사용할 수 있다.
왜냐하면, 노란색이 하나도 포함되어 있지 않은 가로줄은 모두 갈색 격자로 이루어져 있다는 소리인데, 이는 맨 첫 줄과 맨 마지막 줄에서만 나타난다. 이들은 가로 한 줄의 격자 수마큼 이루어져 있다.
문제에서 요구하는 타일에 부합하는가?
def is_saw_carpet(yellow, div, brown):
if get_total_grid(yellow, div) - yellow != brown:
return False
return True노란색 격자 개수에 맞추어서 전체 격자 수를 구했으므로, 해당 타일에 있는 갈색 격자 수가 문제에서 요구한 격자 수와 동일한지 비교하여, 동일하다면 True를 반환한다.
가로와 세로 길이를 구해 반환
def get_carpet_row_col(yellow, div):
row = get_one_row_include_yellow(yellow // div)
col = div + 2
return [row, col]문제에서 요구한 카펫이 맞다면, 카펫의 가로 길이와 세로 길이를 구해 반환한다.
solution
def solution(brown, yellow):
if is_saw_carpet(yellow, 1, brown):
return get_carpet_row_col(yellow, 1)
for div in range(2, int(sqrt(yellow)) + 1):
if not (yellow % div) and (yellow // div) >= div:
if is_saw_carpet(yellow, div, brown):
return get_carpet_row_col(yellow, div)
if (yellow // div) != div and div >= (yellow // div):
if is_saw_carpet(yellow, (yellow // div)):
return get_carpet_row_col(yellow, (yellow // div))임의로 brown과 yellow의 수가 주어졌을 때 모든 yellow를 한 줄로 늘어놓는 경우라면, 문제에서 요구하는 카펫으로서의 조건은 만족한다. 그래서 먼저 이 경우를 수행한다.
만약 yellow를 한 줄로 늘어놓는 경우가 아니라면, 약수의 관계를 생각할 수 있다. 결국, yellow는 직사각형의 모양으로 가운데에 위치해야 한다.
만약 한 줄로 나열하는 것이 아닌 여러 줄로 나열해야 한다면, 1과 자신을 제외(가로 길이 >= 세로 길이 조건으로 인해)한 약수의 조합으로 만들 수 있다.
다만, 약수일 때라 하더라도 가로 길이 >= 세로 길이의 조건을 만족해야 하므로, yellow / div의 값이 div보다 작다면 해당 조건을 만족할 수 없다. 그래서 조건문에 해당 조건을 추가해 불필요한 함수 호출을 막았다.
약수는 yellow의 제곱근까지 반복문을 돌리고, yellow를 그 수로 나눈 값을 또 한 번 검사했다(이 경우는 2 X 4와 4 X 2라고 생각하면 된다). 다만, 이 경우 2 X 2와 같이 뒤집어도 똑같은 경우이거나 가로 길이 >= 세로 길이 조건을 만족하지 못하는 경우는 함수 호출이 불필요하므로 실행시키지 않았다.
다른 사람의 풀이
def solution(brown, yellow):
x = (brown + 4 + ((brown + 4) ** 2) - 16 * (brown + yellow)) ** 0.5 / 4
y = (brown + yellow) // x
return [max(x, y), min(x, y)]코드 출처 : [프로그래머스] 카펫 in python - 슈퍼짱짱
전체 격자의 수는 brown + yellow로 구할 수 있다(나는 왜 이 당연한 생각을 못했지?). 또한 (x - 2) * (y - 2) = yellow다.
이 두 방정식을 연립방정식으로 풀어서, 나온 식을 근의 공식으로 풀면 x, y를 구할 수 있다. 가로 길이 >= 세로 길이 조건에 의해 둘 중 큰 값을 가로로, 작은 값을 세로로 한 리스트를 반환하면 문제를 해결할 수 있다.
