문제 설명
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): total = brown+yellow rows = [(total) // c for c in range(3,(total)//3 + 1) if (total) % c == 0] for row in rows: col = (total) // row if 2*(row+col-2) == brown: return [row, col]
정확성 테스트: ~26.24ms / 10.3MB
수학적인 접근이 필요한 문제였다.
brown, yellow를 입력 받을 때, row와 column을 출력해야 하는데 이때 매개로 하는 것이 총 격자의 수이다.
총 격자의 수를 total이라 하면 total은 brown + yellow과 같다.
row와 column의 곱과도 같아야한다.
여기서 주목할 점은 brown과 yellow를 row와 column으로 바로 표현할 수 있다는 점이다.
brown은 테두리 격자의 수이고 (row-1)+(column-1)+(row-1)+(column-1), 즉 2*(row+column-2)이다.
yellow는 가장 바깥 한 칸씩을 제외한 격자의 수로 (row-2)*(column-2)와 같다.
(yellow가 0보다 크려면 row와 column이 3 이상이어야 한다는 것, 그리고 row와 column으로 표현한 yellow와 brown의 식을 더하면 row*column이 된다는 것도 덤으로 알 수 있다.)
이 사실을 토대로 코딩을 하면 된다.
total에 brown+yellow를 대입한다.
row가 될 수 있는 값을 리스트에 담아야 하는데, total이 c(column에 해당한다.)로 나눠 떨어질 때의 몫을 리스트 rows에 담는다.
c는 3 이상 total//3 이하인 값이다. row와 column 모두 3 이상이어야 하기 때문이다.
rows는 내림차순으로 정렬돼 있는 리스트이기 때문에 큰 수에서 작은 수 순으로 탐색을 할 것이다.
rows가 col보다 커야되기 때문에 내림차순 정렬 돼 있는 것이 탐색하기에 좋다.
rows의 row에 대해 col은 total을 row로 나눈 몫이고 2*(row+column-2)가 brown과 같다면 조건을 만족시키기 때문에 이 때 바로 [row, col]을 반환한다.
사실 row가 col보다 크다는 조건만 없다면, row가 될 수 있는 값은 반대로 col도 될 수 있다.
4*3과 3*4를 생각해 보면 될 것 같다.
어쨌든 위의 코드에서 row가 col보다 크든 안 크든 rows에서 row의 인덱스가 r일 때 col은 rows[-r-1]이라고도 표현할 수 있다.
효율에는 별 차이가 없기 때문에 가독성이 좋은 지금 방식을 택했다.
