[백준_19640]화장실의 규칙 with Python

백준(BOJ) 시뮬레이션 문제집: 화장실의 규칙(골드 5)

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

19640번: 화장실의 규칙

 

1. 알고리즘

처음에 단순히 생각해서 시간초과가 났었다. 이것때문에 고생 좀 했지만...우선순위 큐 잘 사용해서 계속 앞 사람에 대해 찾지 않도록 하면 통과할 것이라고 생각함.

• 대기하는 사람만큼 입력을 받아 서게 될 줄번호를 계산하고 해당 줄에 (근무일수*(-1), 화장실이 급한 정도*(-1), 줄 번호, 사람 번호) 형태로 데이터를 삽입
• 우선순위 큐를 선언, 큐에 각 줄의 가장 맨 앞 사람을 대기줄 리스트에서 뽑아 삽입함.
• 화장실에 간 사람이 데카일 때까지 while 반복
  • 큐에서 가장 우선순위가 높은 사람을 뽑아 화장실에 보냄
  • 화장실에 간 사람+1
  • 화장실에 간 사람이 서 있던 줄의 두번째로 서 있던 사람(=가장 앞 순서로 올 사람)을 뽑아 큐에 추가
• 데카 앞에 몇 사람이 화장실에 갔는지 출력

 

 

2. 유의사항

• 우선순위에 맞게 정렬할 때, 매번 앞 줄의 사람을 찾으면 시간초과 문제가 날 것.

 

 

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

• 시간초과
  • 매번 앞 줄 사람 찾기 > 우선순위 큐에 맨 앞 사람들 넣어놓고, 갱신되는 사람 줄에서만 추가하기

  • #시간초과 코드
    
    while worker != (K+1):
        #대기줄의 가장 앞 사람을 뽑아옴
        worker_candidate = [wl[0] for wl in waiting_lines if wl and wl[0]]
        #정렬
        worker_candidate.sort(reverse=True)
        #가장 맨 앞의 사람을 화장실에 보낼 직원으로 선정
        out_worker = worker_candidate[0]
    	
        #화장실에 간 직원을 대기열에서 삭제
        waiting_lines[(M-out_worker[2])].popleft()
        #화장실에 간 직원의 사람번호
        worker = out_worker[3]
        #화장실에 간 사람+1
        count += 1

• 우선순위 큐 정렬
  • 각 값마다 크고 작은 수의 우선순위가 달랐다. > 클 수록 우선순위가 높은 경우에는 -1을 곱했음

 

 

4. 소스코드

자세한 설명은 주석 참조

import sys
from collections import deque
from queue import PriorityQueue
 
 
input_func = sys.stdin.readline
if __name__ == '__main__':
    N, M, K = map(int, input_func().split())
    waiting_lines, idx = [deque() for _ in range(M)], 0
    #사람 수만큼 반복, 대기줄에 넣어줌
    for n in range(N):
        D, H = map(int, input_func().split())
        #줄번호 계산
        line_number = idx%M
        #대기줄의 줄번호에 사람(-근무일수, -급한 정도, 줄번호, 사람번호) 추가
        waiting_lines[line_number].append((D*(-1), H*(-1), line_number, n+1))
        idx += 1
    
    #화장실에 갈 후보군 우선순위 큐 선언
    out_queue = PriorityQueue()
    #맨 처음의 후보들 큐에 삽입
    for idx in range(M):
        if waiting_lines[idx]:
            next_worker = waiting_lines[idx].popleft()
            out_queue.put(next_worker)
    
    worker, count = -1, 0
    #화장실에 간 직원이 데카가 아닐 때 반복
    while worker != (K+1):
        #우선순위 큐에서 가장 우선순위가 높은 직원 데이터를 빼낸다.
        _, _, out_worker_line, worker = out_queue.get()
        #화장실에 간 사람+1
        count += 1
        #만약 화장실에 간 직원이 서 있던 줄에 다음 사람이 줄 서 있으면
        if waiting_lines[out_worker_line]:
            #그 줄의 다음 사람 데이터를 뽑아와 큐에 삽입
            next_worker = waiting_lines[out_worker_line].popleft()
            out_queue.put(next_worker)
 
    #전체 화장실에 간 사람 - 데카 출력
    print(count-1)

 

5. 고민