17178: 줄서기

ewillwin·2023년 6월 23일
0

Problem Solving (BOJ)

목록 보기
85/230

import sys
from collections import deque

N = int(input())
people = deque([])
for _ in range(N):
	tmp = list(sys.stdin.readline()[:-1].split())
	for t in tmp:
		tmp_element = t.split('-')
		people.append((tmp_element[0], int(tmp_element[1])))

order = sorted(people); order = deque(order) #입장 순서
wait = [] #대기 공간 (stack)
while people:
	person = people.popleft()
	if person == order[0]: #입장할 수 있으면 입장
		order.popleft()
		#print("줄->입장"); print(people); print(wait)
	else: #순서가 맞지 않아서 입장할 수 없는 경우
		if wait:
			wait_person = wait.pop()
			if wait_person == order[0]: #대기 공간에 입장할 수 있는 사람이 있는 경우
				order.popleft()
				people.appendleft(person)
				#print("대기->입장"); print(people); print(wait)
			else: #대기 공간에 입장할 수 있는 사람이 없는 경우
				wait.append(wait_person)
				wait.append(person)
				#print("줄->대기"); print(people); print(wait)
		else: #대기 공간에 입장할 수 있는 사람이 없는 경우
			wait.append(person)
			#print("줄->대기"); print(people); print(wait)
	#print(order)
	#print()

if wait: #종료조건(BAD)
	wait_sorted = sorted(wait, reverse=True)
	if wait_sorted != wait:
		print("BAD")
		exit()
print("GOOD")
  • stack과 queue, 조건 분기만 조금 신경쓰면 쉬운 문제
  • people이 빌 때까지 while문 순회. 마지막에 남아있는 wait 리스트를 역순으로 정렬한 결과가 order 리스트와 다르다면 BAD를 출력하고 프로세스 종료
  • people: 줄에 기다리고 있는 사람 (queue로 구현)
  • order: 입장 순서 (queue로 구현)
  • wait: 대기 공간에 있는 사람 (stack으로 구현)
➜  연습용 python3 test.py
1
G-555 B-203 A-102 A-504 C-719
줄->대기
deque([('B', 203), ('A', 102), ('A', 504), ('C', 719)])
[('G', 555)]
deque([('A', 102), ('A', 504), ('B', 203), ('C', 719), ('G', 555)])

줄->대기
deque([('A', 102), ('A', 504), ('C', 719)])
[('G', 555), ('B', 203)]
deque([('A', 102), ('A', 504), ('B', 203), ('C', 719), ('G', 555)])

줄->입장
deque([('A', 504), ('C', 719)])
[('G', 555), ('B', 203)]
deque([('A', 504), ('B', 203), ('C', 719), ('G', 555)])

줄->입장
deque([('C', 719)])
[('G', 555), ('B', 203)]
deque([('B', 203), ('C', 719), ('G', 555)])

대기->입장
deque([('C', 719)])
[('G', 555)]
deque([('C', 719), ('G', 555)])

줄->입장
deque([])
[('G', 555)]
deque([('G', 555)])

GOOD
➜  연습용 python3 test.py
2
J-123 I-808 B-203 A-102 A-4
C-19 G-999 G-555 G-902 I-111
줄->대기
deque([('I', 808), ('B', 203), ('A', 102), ('A', 4), ('C', 19), ('G', 999), ('G', 555), ('G', 902), ('I', 111)])
[('J', 123)]
deque([('A', 4), ('A', 102), ('B', 203), ('C', 19), ('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->대기
deque([('B', 203), ('A', 102), ('A', 4), ('C', 19), ('G', 999), ('G', 555), ('G', 902), ('I', 111)])
[('J', 123), ('I', 808)]
deque([('A', 4), ('A', 102), ('B', 203), ('C', 19), ('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->대기
deque([('A', 102), ('A', 4), ('C', 19), ('G', 999), ('G', 555), ('G', 902), ('I', 111)])
[('J', 123), ('I', 808), ('B', 203)]
deque([('A', 4), ('A', 102), ('B', 203), ('C', 19), ('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->대기
deque([('A', 4), ('C', 19), ('G', 999), ('G', 555), ('G', 902), ('I', 111)])
[('J', 123), ('I', 808), ('B', 203), ('A', 102)]
deque([('A', 4), ('A', 102), ('B', 203), ('C', 19), ('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->입장
deque([('C', 19), ('G', 999), ('G', 555), ('G', 902), ('I', 111)])
[('J', 123), ('I', 808), ('B', 203), ('A', 102)]
deque([('A', 102), ('B', 203), ('C', 19), ('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

대기->입장
deque([('C', 19), ('G', 999), ('G', 555), ('G', 902), ('I', 111)])
[('J', 123), ('I', 808), ('B', 203)]
deque([('B', 203), ('C', 19), ('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

대기->입장
deque([('C', 19), ('G', 999), ('G', 555), ('G', 902), ('I', 111)])
[('J', 123), ('I', 808)]
deque([('C', 19), ('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->입장
deque([('G', 999), ('G', 555), ('G', 902), ('I', 111)])
[('J', 123), ('I', 808)]
deque([('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->대기
deque([('G', 555), ('G', 902), ('I', 111)])
[('J', 123), ('I', 808), ('G', 999)]
deque([('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->입장
deque([('G', 902), ('I', 111)])
[('J', 123), ('I', 808), ('G', 999)]
deque([('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->입장
deque([('I', 111)])
[('J', 123), ('I', 808), ('G', 999)]
deque([('G', 999), ('I', 111), ('I', 808), ('J', 123)])

대기->입장
deque([('I', 111)])
[('J', 123), ('I', 808)]
deque([('I', 111), ('I', 808), ('J', 123)])

줄->입장
deque([])
[('J', 123), ('I', 808)]
deque([('I', 808), ('J', 123)])

GOOD
➜  연습용 python3 test.py
2
J-123 I-808 B-203 A-102 A-4
C-19 G-999 G-555 I-111 G-902
줄->대기
deque([('I', 808), ('B', 203), ('A', 102), ('A', 4), ('C', 19), ('G', 999), ('G', 555), ('I', 111), ('G', 902)])
[('J', 123)]
deque([('A', 4), ('A', 102), ('B', 203), ('C', 19), ('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->대기
deque([('B', 203), ('A', 102), ('A', 4), ('C', 19), ('G', 999), ('G', 555), ('I', 111), ('G', 902)])
[('J', 123), ('I', 808)]
deque([('A', 4), ('A', 102), ('B', 203), ('C', 19), ('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->대기
deque([('A', 102), ('A', 4), ('C', 19), ('G', 999), ('G', 555), ('I', 111), ('G', 902)])
[('J', 123), ('I', 808), ('B', 203)]
deque([('A', 4), ('A', 102), ('B', 203), ('C', 19), ('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->대기
deque([('A', 4), ('C', 19), ('G', 999), ('G', 555), ('I', 111), ('G', 902)])
[('J', 123), ('I', 808), ('B', 203), ('A', 102)]
deque([('A', 4), ('A', 102), ('B', 203), ('C', 19), ('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->입장
deque([('C', 19), ('G', 999), ('G', 555), ('I', 111), ('G', 902)])
[('J', 123), ('I', 808), ('B', 203), ('A', 102)]
deque([('A', 102), ('B', 203), ('C', 19), ('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

대기->입장
deque([('C', 19), ('G', 999), ('G', 555), ('I', 111), ('G', 902)])
[('J', 123), ('I', 808), ('B', 203)]
deque([('B', 203), ('C', 19), ('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

대기->입장
deque([('C', 19), ('G', 999), ('G', 555), ('I', 111), ('G', 902)])
[('J', 123), ('I', 808)]
deque([('C', 19), ('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->입장
deque([('G', 999), ('G', 555), ('I', 111), ('G', 902)])
[('J', 123), ('I', 808)]
deque([('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->대기
deque([('G', 555), ('I', 111), ('G', 902)])
[('J', 123), ('I', 808), ('G', 999)]
deque([('G', 555), ('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->입장
deque([('I', 111), ('G', 902)])
[('J', 123), ('I', 808), ('G', 999)]
deque([('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->대기
deque([('G', 902)])
[('J', 123), ('I', 808), ('G', 999), ('I', 111)]
deque([('G', 902), ('G', 999), ('I', 111), ('I', 808), ('J', 123)])

줄->입장
deque([])
[('J', 123), ('I', 808), ('G', 999), ('I', 111)]
deque([('G', 999), ('I', 111), ('I', 808), ('J', 123)])

BAD
profile
ewillwin
💼 Software Engineer @ LG Electronics | 🎓 SungKyunKwan Univ. CSE
이전 포스트

21608: 상어 초등학교

다음 포스트

14719: 빗물

0개의 댓글