첫 n개의 자연수가 정렬되지 않은 상태로 들어 있는 큐(Queue)가 있다고 가정해 보겠습니다. 이 문제의 목표는 주어진 큐의 요소들을 스택을 중간 버퍼로 활용하여 다른 큐에 비내림차순(non-decreasing)으로 정렬할 수 있는지 판별하는 것입니다.
허용되는 연산
이 문제를 해결하기 위해 다음 세 가지 연산만 사용할 수 있습니다.
- 스택에 요소를 push 하거나 pop 하기
- 주어진 큐에서 요소를 삭제(dequeue)하기
- 다른 큐에 요소를 삽입(enqueue)하기
예를 들어 입력이 Que = [6, 1, 2, 3, 4, 5]라면 출력은 True입니다. 먼저 맨 앞의 6을 큐에서 꺼내 스택에 넣고(push), 남은 요소 1~5를 모두 두 번째 큐로 옮긴 뒤, 스택에서 6을 꺼내(pop) 두 번째 큐의 맨 뒤에 추가하면 새 큐는 [1, 2, 3, 4, 5, 6]이 되어 비내림차순으로 정렬되기 때문입니다.
해결 알고리즘
핵심 아이디어는 다음에 나와야 할 값을 추적하는 변수 exp_val(expected value)입니다. 큐의 요소를 하나씩 처리하면서 기대 값과 일치하면 바로 통과시키고, 일치하지 않으면 스택에 임시 보관합니다.
먼저 초기값을 설정합니다.
n:= 큐의 크기stk:= 새로운 빈 스택exp_val:= 1 (다음으로 기대되는 값)front:= null
그다음, 큐가 빌 때까지 다음 과정을 반복합니다.
- 큐의 맨 앞 요소를
front에 저장한 뒤 큐에서 제거합니다. front가exp_val과 같다면exp_val을 1 증가시킵니다. (두 번째 큐에 곧바로 올바른 순서로 배치됨)- 같지 않다면 다음을 수행합니다.
- 스택이 비어 있으면
front를 스택에 push 합니다. - 스택이 비어 있지 않은데 스택의 top이
front보다 작다면, 나중에 꺼낼 때 순서가 깨지므로 False를 반환합니다. - 그 외의 경우에는
front를 스택에 push 합니다.
- 스택이 비어 있으면
- 스택이 비어 있지 않고 스택의 top이
exp_val과 같은 동안 계속 pop 하며exp_val을 1씩 증가시킵니다.
모든 과정이 끝난 후 exp_val - 1이 n과 같고 스택이 비어 있다면 True를, 그렇지 않다면 False를 반환합니다.
Python 구현 예제
from queue import Queue
def solve(que):
n = que.qsize()
stk = []
exp_val = 1
front = None
while (not que.empty()):
front = que.queue[0]
que.get()
if (front == exp_val):
exp_val += 1
else:
if (len(stk) == 0):
stk.append(front)
elif (len(stk) != 0 and stk[-1] < front):
return False
else:
stk.append(front)
while (len(stk) != 0 and stk[-1] == exp_val):
stk.pop()
exp_val += 1
if (exp_val - 1 == n and len(stk) == 0):
return True
return False
que = Queue()
items = [6, 1, 2, 3, 4, 5]
for i in items:
que.put(i)
print(solve(que))입력
[6, 1, 2, 3, 4, 5]출력
True복잡도 및 정리
이 알고리즘은 큐의 각 요소를 정확히 한 번씩 처리하며, 각 요소는 최대 한 번 스택에 들어갔다가 나오므로 시간 복잡도는 O(n)입니다. 스택에 최악의 경우 모든 요소가 저장될 수 있으므로 공간 복잡도 역시 O(n)입니다. 기대 값과의 일치 여부와 스택 top의 대소 관계만 확인하면 되기 때문에 구현이 단순하면서도 효율적인 판별 방법입니다.