문제 개요
서로 다른 크기의 n개 큐브가 담긴 배열 nums가 있고, 이 큐브들은 가로로 나란히 놓여 있다고 가정해 봅시다. 우리는 이 큐브들을 세로로 쌓아 하나의 탑을 만들어야 합니다. 단, 새로 올리는 큐브는 다음 조건을 만족해야 합니다.
- i번째 큐브가 j번째 큐브 위에 놓인다면, 아래에 있는 j번째 큐브의 한 변의 길이는 i번째 큐브의 한 변의 길이보다 크거나 같아야 합니다.
세로로 쌓는 과정에서는 중간에 있는 큐브를 가져올 수 없고, 배열의 왼쪽 끝 또는 오른쪽 끝에 있는 큐브만 선택할 수 있습니다. 이 조건 안에서 모든 큐브를 성공적으로 쌓을 수 있는지 판별해야 합니다.
예를 들어 입력이 nums = [1,2,3,7,8]이라면 출력은 True입니다. 오른쪽 끝부터 차례대로 큐브를 가져와 쌓으면 8 → 7 → 3 → 2 → 1 순서로 내림차순이 되어 조건을 만족하기 때문입니다.
해결 접근 방법
이 문제는 양방향 큐(deque)를 활용하면 효율적으로 해결할 수 있습니다. 매 시점 남아 있는 큐브들의 양쪽 끝만 비교하여 더 작은 쪽을 탑 위에 올리면 됩니다. 구체적인 단계는 다음과 같습니다.
- n을 nums의 길이로 설정합니다.
- nums의 원소들로 양방향 큐 d를 만듭니다.
- flag를 True로, prev를 0으로 초기화합니다.
- d가 빌 때까지 다음 과정을 반복합니다.
- first는 d의 맨 앞 원소, last는 d의 맨 뒤 원소입니다.
- prev가 0이 아니면서 first 또는 last가 prev보다 크다면, 쌓는 것이 불가능하므로 flag를 False로 바꾸고 반복을 종료합니다.
- first가 last보다 크거나 같으면 왼쪽 끝 원소를 꺼내 prev에 저장하고, 그렇지 않으면 오른쪽 끝 원소를 꺼내 prev에 저장합니다.
- flag가 여전히 True이면 True를 반환하고, 그렇지 않으면 False를 반환합니다.
구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
from collections import deque
def solve(nums):
n = len(nums)
d = deque(nums)
flag = True
prev = 0
while d:
first = d[0]
last = d[-1]
if prev != 0 and (first > prev or last > prev):
flag = False
break
if first >= last:
prev = d.popleft()
else:
prev = d.pop()
return flag
nums = [1,2,3,7,8]
print(solve(nums))입력
[1,2,3,7,8]
출력
True
시간 복잡도 분석
이 알고리즘은 매 반복마다 큐에서 원소를 하나씩 제거하므로 전체 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 입력을 담기 위한 양방향 큐 때문에 O(n)입니다. 매 순간 양쪽 끝의 값만 비교하므로 어떤 순서로 큐브를 가져와야 하는지 직관적으로 판단할 수 있다는 점이 이 접근 방식의 장점입니다.