[Algorithm] 백준 12789 - 도키도키 간식드리미 in Python(파이썬)

💡 백준 12789:

스택 기본 구조 활용

🌱 코드 in Python

알고리즘: Stack

이번 문제는 스택 자료구조를 다루는 기본 문제였다

그다지 어려운 문제였는데 또 문제를 정확히 이해하지 않고 풀어서 아무도 빠트리지 않은 함정에 또 빠져버렸다
내가 처음했던 실수는 처음 줄 선 곳이 먼저 빠져나가고 서브 대기라인이 빠져나간다고 생각해서 발생한 문제였다

import sys

n = int(sys.stdin.readline())
wait = list(map(int, sys.stdin.readline().split()))

target = 1
tmp = []
for i in range(n):
	if wait[0] == target:
		wait.pop(0)
		target += 1
	else:
		tmp.append(wait.pop(0))
		if i != 0 and tmp[-1] > tmp[-2]:
			print("Sad")
			sys.exit()
print("Nice")

그래서 위와 같은 코드를 짰다..
target이 아니면 tmp에 갖다 넣고 tmp 요소만 비교했는데, 이렇게 하면 2 1 3 과 같은 테스트케이스가 올바르게 나오지 않는다
2가 서브 대기줄에 들어가고 1이 빠져나간 후 서브 대기줄에서 2를 뺄 수 있는데, 내 코드의 경우 그러한 경우를 고려하지 않았다

따라서 아래와 같은 코드로 변경하였다

import sys

n = int(sys.stdin.readline())
wait = list(map(int, sys.stdin.readline().split()))
target = 1 # 찾아야 하는 간식 받을 사람
tmp = []
while target != n: # 마지막 대기자를 찾을 때 까지
	if wait and wait[0] == target: # wait 큐의 처음이 간식 받을 사람일 때
		wait.pop(0) # 간식받을 사람 pop
		target += 1 # 다음 대기자로 변경
	elif tmp and tmp[-1] == target: # tmp 스택의 마지막이 간식 받을 사람일 때
		tmp.pop() # 간식받을 사람 pop
		target += 1 # 다음 대기자로 변경
	else:
		tmp.append(wait.pop(0)) # wait 큐의 처음과 tmp 스택의 마지막 사람도 간식 받을 사람이 아닐 때
		if len(tmp) > 1 and tmp[-1] > tmp[-2]: # tmp에 2명 이상의 대기자가 있고 tmp의 마지막 원소가 그 전 원소보다 클 경우
			print("Sad") # 에러 처리
			sys.exit() # 프로그램 종료
if (len(wait) == 1 and len(tmp) == 0 and target == wait[0]) or (len(wait) == 0 and len(tmp) == 1 and target == tmp[0]) : # 두 대기줄 중 하나만 하나의 원소가 남아있고 그 마지막 원소가 target과 일치할 경우
	print("Nice")
else:
	print("Sad")

이 코드에서는 wait와 tmp 2개에서 모두 target을 비교한다
wait는 queue, tmp는 stack으로 활용하여 문제를 풀었다

마지막 예외처리는 혹여 첫번째 n값보다 배열 길이가 클 경우 or 마지막 값이 target값이 아닌 경우가 있을까 해서 했다..

그런데 이렇게 굳이 두 스택을 비교할 필요가 없었다!

import sys

input = sys.stdin.readline
n = int(input())
wait = list(map(int, input().split()))
tmp = []
target = 1
for i in wait:
	tmp.append(i)
	while tmp and tmp[-1] == target: # tmp 스택 하나로 비교
		tmp.pop()
		target += 1
	if len(tmp) > 1 and tmp[-1] > tmp[-2]:
		print("Sad")
		sys.exit()
if tmp:
	print("Sad")
else:
	print("Nice")

그래서 변경한 코드! 이렇게 하면 스택을 하나로 비교할 수 있다
tmp 스택에 넣자마자 바로 비교하면서 빼거나, 빼지 못할 경우 전 원소와 비교하며 에러를 바로 확인할 수 있다

마지막 if문은 위와 같이 배열에 target값이 없을 경우 예외처리를 해주었다

🧠 기억하자

1. 문제를 잘 읽자!

2. 문제 이름 왜 저래 ㅡㅡ 두근두근 간식드리미라 하라고~!

백준 12789 바로가기