👀 문제
12789번: 도키도키 간식드리미 ✨ 실버 3
인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다.
그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다.
그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다.
자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다.
만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다.
사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라.
현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.
위 예제는 다음 그림과 같이 움직였을 때 모두가 순서대로 간식을 받을 수 있다.
승환이가 무사히 간식을 받을 수 있으면 "Nice"(따옴표는 제외)를 출력하고 그렇지 않다면 "Sad"(따옴표는 제외)를 출력한다.
🔑 키포인트
스택 자료 구조
⛑️ 실수했던 점
1️⃣ 한 명 대기줄의 대기자 번호 미확인
한 명만 설 수 있는 대기줄에 다음 번호인 사람이 맨 앞에 서 있으면 간식을 받으러 가야 하는데, 처음에 이 코드를 구현하지 않았다.
2️⃣ 한 명 대기줄에 마지막 한 명이 남아 있는 경우 간과
기존의 대기줄에 사람이 없는 경우 while문을 break하도록 했기 때문에, 한 명 대기줄에 마지막 번호인 한 명이 남아 있을 수 있다. 이 사실을 반례를 통해 깨닫고 코드에 추가해 주었다.
✍️ 코드
import sys
input = sys.stdin.readline
N = int(input())
numbers = list(map(int, input().split()))
wait = [] # 한 명씩 설 수 있는 공간
order = 1
result = ""
# 찾았던 반례
# 5
# 5 3 1 2 4
while True:
# 대기줄에 아무도 없으면 break
if len(numbers) == 0:
break
if numbers[0] == order:
numbers.pop(0)
order += 1 # 다음 순서
elif len(wait) != 0 and wait[0] == order:
wait.pop(0)
order += 1
else:
wait.insert(0, numbers.pop(0))
# 한 명 씩만 설 수 있는 대기줄 확인
if len(wait) == 0 or len(wait) == 1: # 대기줄에 아무도 없거나 한 명일 때
result = "Nice"
else: # 대기줄에 여려명 있는 경우
for i in range(len(wait)-1):
# 앞 숫자가 뒤 숫자 -1이 아니면
# 예) 3, 4, 5여야 함
if wait[i] != wait[i+1]-1:
result = "Sad"
break
else:
result = "Nice"
print(result)