https://programmers.co.kr/learn/courses/30/lessons/42842
코딩테스트 연습 - 카펫
Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과
programmers.co.kr
쉽게 풀었지만 코드가 많이 너저분하다.
효율성은 나쁘진 않다. O(N)
1. 갈색과 노란색 카펫수가 제공됐을때 전체 카펫은 갈색+노란색 이고 조합할 수 있는 모든 가로x세로 를 구하기 위해 약수를 구한다.
2. 약수 리스트가 하나 밖에 없다면 정답은 (약수1 x 약수1) 이다.
3. 약수 리스트가 두개면 크기에 따라 (약수1 x 약수2) 또는 (약수2 x 약수1) 이다.
4. 약수 리스트가 세개 이상이면 해당 하는 타일을 계산했을때 가운데 남는 타일 수가 제공된 yellow 와 같다면 정답이다.
예를들어 갈색 12 노란색 4가 제공됐을때 모든 약수를 구하면 [2, 3, 4, 6, 8, 12] 이다.
가능한 가로x세로 조합은 [2x12, 3x8, 4x6] 이다.
이때 테두리 타일의 갯수를 구하는 공식이 (((a - 2) * 2) + (b * 2)) 이고 전체 타일에서 테두리 타일 수를 빼면 남는 타일이 제공된 yellow 와 같다면 정답이다.
(((a - 2) * 2) + (b * 2)) 가 왜 테두리를 구하는 공식이냐하면
4x4 인 경우 가로는 4 세로는 4 이라고 해보자.
(((4 - 2) * 2) + (4 * 2)) 는 테두리 타일의 갯수가 된다.
| 세로 (가로-1) | 가로 | 가로 | 세로 (가로-1) |
| 세로 | 노란 격자 | 노란 격자 | 세로 |
| 세로 | 노란 격자 | 노란 격자 | 세로 |
| 세로 (가로-1) | 가로 | 가로 | 세로 (가로-1) |
from collections import deque
def solution(brown, yellow):
total_tile = brown + yellow
temp = deque()
for i in range(2, (total_tile // 2) + 1):
if total_tile % i == 0:
temp.append(i)
if len(temp) == 1:
return [temp[0], temp[0]]
elif len(temp) == 2:
if temp[0] >= temp[1]:
return [temp[0], temp[1]]
return [temp[1], temp[0]]
else:
while temp:
a = temp.popleft()
b = a
if temp:
b = temp.pop()
y = total_tile - (((a - 2) * 2) + (b * 2))
if y == yellow:
if a >= b:
return [a, b]
return [b, a]
return 0