[백준_17178]줄서기 with Python

백준(BOJ) 시뮬레이션 문제집: 줄서기(골드 5)

문제 출처: https://www.acmicpc.net/problem/17178

17178번: 줄서기

 

1. 알고리즘

문제 설명대로만 풀면 된다. 데이터 참조 인덱스 체크 부분이 좀 귀찮고, 알고리즘 자체는 쉬웠던 문제

• 입력받은 한 줄의 티켓 데이터를 (구역, 번호)데이터로 나누어 deque, list형식으로 deque과 list에 넣어줌.
• 위에서 만든 티켓 리스트를 정렬하여 전체 티켓의 입장 순서를 나열한 list를 만듦.
• 티켓 입장 순서 list에 데이터가 존재하는 동안(=입장해야할 사람이 있는 동안) while 반복
  • 기다리는 줄이 있고, 그 줄의 가장 앞 줄이 있고, 그 앞 줄의 맨 앞 사람이 입장해야 하는 사람
    • 입장 순서 list의 맨 앞 사람 입장, 기다리는 줄 가장 앞 줄의 맨 앞 사람 입장
  • 대기 공간에 사람이 있고, 대기 공간의 가장 최근 사람이 입장해야 하는 사람
    • 입장 순서 list의 맨 앞 사람 입장, 대기 공간 가장 마지막 사람 입장
  • 기다리는 줄 맨 앞, 대기 공간 맨 마지막 모두 입장해야 하는 사람이 아닌 경우
    • 기다리는 줄 사람이 없다면 while문 break
    • 기다리는 줄의 가장 앞 줄의 맨 앞 사람을 대기공간으로 이동
  • 기다리는 줄이 있고, 기다리는 줄의 맨 앞 줄이 없고, 줄이 2줄 이상인 경우
    • 기다리는 줄의 0번 빈 deque을 삭제
• 입장 순서 list에 따라 데이터 출력
  • 모두 입장했으면 GOOD 출력
  • 입장하지 못한 티켓이 있으면 BAD 출력

 

 

2. 유의 사항

• 기다리는 줄은 0번 줄의 0번 사람만 이동(입장/대기공간 이동)가능
• 대기공간 사람은 콘서트 입장만 가능(기다리는 줄로 복귀 불가능)

 

3. 어려웠던 점, 해결 방법

 

 

4. 소스코드

자세한 설명은 주석 참조

import sys
from collections import deque
 
 
input_func = sys.stdin.readline
if __name__ == '__main__':
    N = int(*map(int, input_func().split()))
    #기다리는 줄, 입장 순서 리스트 생성
    waitings, entrance_order = deque(), []
    for _ in range(N):
        waiting_people = list(map(str, input_func().split()))
        #split으로 구역, 번호 분리 후 임시 덱 생성 
        temp_waitings = deque()
        for wp in waiting_people:
            space, number = wp.split('-')
            temp_waitings.append((space, int(number)))
        #기다리는 줄은 덱 그대로, 입장 순서 리스트에는 리스트로
        waitings.append(temp_waitings)
        entrance_order.append(list(temp_waitings))
    
    #(구역, 번호)데이터 sorting 후 deque 자료형
    entrance_order = deque(sorted(sum(entrance_order, [])))
    
    #콘서트 입장
    temp = []
    while entrance_order:   #입장할 티켓만큼 반복
        
        #현재 입장해야 하는 티켓
        person = entrance_order[0]
        
        #기다리는 줄 사람 확인
        if waitings and waitings[0] and person == waitings[0][0]:
            entrance_order.popleft()
            waitings[0].popleft()
        
        #대기 공간 사람 확인
        elif temp and person == temp[-1]:
            temp.pop()
            entrance_order.popleft()
        
        #입장해야 하는 티켓이 기다리는 줄과 대기 공간에 없는 경우
        else:
            #기다리는 사람이 없을 때, 더 이상 사람을 옮겨 줄 수 없으므로 종료
            if not waitings:
                break
            #기다리는 줄 사람을 대기공간으로 이동
            temp.append(waitings[0].popleft())
        
        #초기 기다리는 줄이 두 줄 이상이고, 현재 가장 앞 줄이 비어 있는 경우 
        if waitings and not waitings[0] and N >= 2:
            waitings.popleft()
 
    #모든 티켓이 입장했으면 GOOD
    if not entrance_order:
        print('GOOD')
    #입장하지 못한 티켓이 있으면 BAD
    else:
        print('BAD')

 

5. 고민

• entrance_order만들 때엔 그냥 extend 쓰면 될 걸 왜 저렇게 했나 몰라