문제가 궁금하시다면 아래의 링크를 눌러주세요!
문제 보러 가기
접근 과정
최대 길이 N이 1000인 배열이 주어진다. 이 사람들이 주어진 번호표의 순서대로 줄을 서야 하는데, 중간의 대기열에 먼저 들어갈수록, 늦게 빠져나오게 되는 부분에서 선입 후출의 성격을 가지는 스택을 사용해야 한다는 것을 생각할 수 있었다.
이런 배열이 주어졌다고 가정해보자
배열의 가장 좌측(줄의 맨 앞에 서 있는) 요소인 5가 가장 먼저 출발하게 된다. 하지만 5는 배열 내에서 최솟값(가장 빠른 번호표)이 아니기 때문에, 간식 줄로 바로 갈 수가 없고 대기열로 이동해야 한다.
같은 방식으로, 요소 4와 3도 동일하게 대기열로 이동하게 된다. 그 뒤 배열 내에서 최솟값인 요소 1을 만나게 되는데, 1은 바로 간식 줄로 이동이 가능하고 그 뒤의 요소 2도 원본 배열 내 남은 요소들 중에서는 그 값이 최소이기 때문에 바로 간식 줄로 이동이 가능하다.
그 후, 대기열의 요소들을 하나씩 검증하며 해당 요소가 간식 줄로 이동이 가능한지 확인하여야 한다. 대기열에 가장 늦게 들어간 요소 3이 제일 먼저 검증의 대상이 되는데, 3은 바로 간식 줄에 진입할 수 있다.
이런 일련의 과정들이 전부 끝나고 난 최종 상태는 아래와 같게 된다. 이 경우는 모두가 간식을 받을 수 있다.
이렇게만 보면 원본 배열의 요소들을 전부 확인하면서 대기열과 간식 줄로 분리하고 난 이후 대기열을 살펴보는 것처럼 보일 수 있지만, 사실 대기열을 확인하는 과정은 원본 배열에서 요소를 하나 뽑아올 때마다 진행되어야 한다.
위의 경우, 요소 1 바로 다음 요소 3보다 대기열에 있는 2가 더 작은 값이기 때문에, 요소 1이 간식 줄로 이동한 이후 대기열에 있는 요소 2를 간식 줄로 옮겨줘야 한다.
그렇다면 이런 과정을 통해 항상 모든 요소들을 번호 순으로 나열할 수 있을까?
이렇게 번호 순으로 나열할 수 없는 경우도 존재한다. 정리하면, 원본 배열에서 하나씩 요소를 꺼내 간식 줄이나, 대기열에 넣는 과정을 전부 마치고 난 시점에서 대기열 스택의 길이가 0이 아닌 경우(요소가 들어있는 경우)는 모든 요소가 번호 순으로 나열되지 못한 경우이다!
풀이
import sys
from collections import deque
def snack(arr):
Q = deque()
Q.extend(arr)
exit = [] # 간식 줄
wait = [] # 대기열
while Q:
number = Q.popleft()
# 현재 간식 줄이 비어있고, 뽑아온 요소가 최솟값이라면
if not exit and number == min(people):
exit.append(number)
else:
if exit:
# 뽑아온 요소가 간식줄 스택 마지막 요소의 바로 다음 번호인 경우
if exit[-1] + 1 == number:
exit.append(number)
else:
wait.append(number)
else:
# 간식 줄이 비어있지만 해당 요소가 최솟값은 아니라면 대기열로 이동
wait.append(number)
while wait:
# 대기열 내의 요소들을 하나씩 뽑아서 검증한다.
waiting_people = wait.pop()
if exit and exit[-1] + 1 == waiting_people:
exit.append(waiting_people)
else:
wait.append(waiting_people)
break
if not wait:
return True
else:
return False
input = sys.stdin.readline
N = int(input())
people = list(map(int, input().split()))
if snack(people):
print("Nice")
else:
print("Sad")통과!
개선
원본 배열에서 가장 좌측의 요소 순으로 뽑아온다는 조건을 보고서 덱을 사용하였는데, 다시 생각해보니 굳이 덱으로 할 필요 없이 리스트로 받아온 이후 [::-1] 슬라이싱을 통해 원본 배열을 뒤집어주면 pop() 메서드를 통해 O(1)의 복잡도로 요소를 꺼내올 수가 있었다.
그리고 간식 줄에 들어갈 수 있는 값인지 검증하는 과정을 간식 줄 스택의 가장 마지막 요소보다 1 큰 값인지(번호 순으로 줄을 서기 때문에) 확인하는 방식으로 진행하였는데, 1로 시작하는 정수형 변수를 하나 선언하고 간식 줄이 채워질 때마다 값을 1씩 증가시켜 뽑아온 요소가 해당 정수 값과 동일한지 확인하는 방식이 더 간단하고, 직관적일 것 같다는 생각이 들었다.
