99클럽 코테 스터디_4기 18일차 TIL

TODAY TIL

 

안녕하세요! 이번 블로그 포스팅에서는 학교 식당 줄 서기 문제를 해결하는 파이썬 코드와 문제 해결 과정을 공유해보려고 합니다. 이 문제는 많은 학생들이 식당에서 줄을 서고, 식사가 준비되는 과정을 처리하면서 최대 대기 인원을 기록하는 문제입니다. 특히, 입력의 개수가 많기 때문에 효율적인 구현이 필요합니다. 함께 문제를 이해하고 해결해봅시다!

문제 설명

학생들이 학교 식당에 도착하고, 식사가 준비되는 총 n개의 정보가 주어집니다. 이 정보는 두 가지 유형으로 이루어져 있습니다:

1. 학생 도착 (유형 1 a): 학생 번호 a가 식당에 도착하여 줄을 섭니다.
2. 식사 준비 (유형 2): 줄의 맨 앞 학생이 식사를 시작합니다.

식당에 도착한 학생은 줄의 맨 뒤에 서게 되며, 식사가 준비되면 줄의 맨 앞에 있는 학생이 식사를 하러 들어갑니다. 우리는 이 과정에서 줄에 서 있는 학생 수가 최대가 되었을 때, 그 순간 줄의 맨 뒤에 있는 학생 번호를 출력해야 합니다.

문제 해결 접근법

이 문제를 해결하기 위해 다음과 같은 접근 방식을 사용했습니다:

• 큐(Queue) 자료구조를 활용해 학생들이 줄을 서고, 식사를 하러 들어가는 과정을 구현합니다. deque 모듈을 사용하면 큐의 양쪽에서 삽입과 삭제가 빠르게 이루어지므로 적합합니다.
• 최대 대기 인원과 그 순간의 줄 맨 뒤 학생 번호를 추적하여 결과를 계산합니다.

코드 구현

아래는 문제를 해결하기 위한 파이썬 코드입니다:

from collections import deque
import sys

n = int(input())
queue = deque()
max_wait = 0
last_student = 100001

for _ in range(n):
    action = sys.stdin.readline().strip()
    if action[0] == '1':  # 학생 도착 (유형 1)
        _, student_number = action.split()
        student_number = int(student_number)
        queue.append(student_number)

        if len(queue) > max_wait:
            max_wait = len(queue)
            last_student = queue[-1]
        elif len(queue) == max_wait:
            if queue[-1] < last_student:
                last_student = queue[-1]

    elif action[0] == '2' and queue:  # 식사 준비 (유형 2)
        queue.popleft()

if max_wait == 0:
    last_student = -1

 

코드 설명

1. 입력 처리 및 초기화
   • n은 총 명령어의 개수를 의미합니다.
   • queue는 학생들이 줄을 서는 대기열을 나타내며, deque()로 초기화됩니다.
   • max_wait는 대기 중인 최대 학생 수를 저장하며, last_student는 그때 줄의 맨 뒤에 있는 학생 번호를 기록합니다.
2. 학생 도착 처리 (유형 1)
   • 학생 번호가 주어지면 해당 번호를 큐의 맨 뒤에 추가합니다.
   • 대기열 길이가 max_wait보다 크다면 이를 갱신하고, last_student를 현재 줄의 맨 뒤 학생 번호로 업데이트합니다.
   • 만약 대기열 길이가 max_wait와 같다면, 줄의 맨 뒤 학생 번호가 더 작은 경우로 갱신합니다.
3. 식사 준비 처리 (유형 2)
   • 식사가 준비되면 큐의 맨 앞에 있는 학생을 제거합니다.
4. 결과 계산
   • 만약 최대 대기 인원이 0이라면, 대기 중인 학생이 없다는 의미로 last_student를 -1로 설정합니다.

문제 해결의 어려움과 해결 방법

이 문제는 주어진 입력의 개수가 최대 100,000개일 수 있기 때문에 효율적인 입력 처리와 큐의 사용이 필수적입니다. sys.stdin.readline()을 사용하여 입력을 빠르게 처리하고, deque를 활용하여 큐 연산을 효율적으로 구현함으로써 런타임 에러를 피할 수 있었습니다.

마무리

이번 포스팅에서는 학생들이 식당에서 줄을 서는 문제를 해결하는 파이썬 코드를 다뤄보았습니다. 큐 자료구조를 사용해 효율적으로 줄 서기와 식사 과정을 처리하고, 최대 대기 인원과 그때의 학생 번호를 찾는 과정에서 발생할 수 있는 여러 가지 상황들을 고려했습니다. 이 코드가 여러분의 이해에 도움이 되었기를 바랍니다!