[백준 / Python] 26042 식당 입구 대기 줄

문제

 

https://www.acmicpc.net/problem/26042

26042번: 식당 입구 대기 줄

 

---

Algorithm

뒤에서 부터 줄을 서고, 앞에서 부터 식사를 시작하러 들어가므로 큐를 사용하면 되는 문제이다.

줄에 서있는 사람이 최대가 될때, 마지막에 대기중인 학생의 번호를 찾으면 되는데, 이때 줄에 서있는 사람이 최대가 되는경우가 여러가지일 경우 마지막에 대기중인 학생의 번호가 최소가 되는 경우를 출력해야 한다.

줄을 큐를 이용하여 구현을 하면 된다고 생각했고, 2단계로 코드를 구성해보았다.

1. 대기줄의 상태를 만들기

2. 문제에서 원하는 출력값 저장하기

로 나타낼 수 있다.

1. 대기줄의 상태를 만들기

큐에 인원이 추가되는것은 간단히 구현이 가능하지만, 따져봐야할것은 인원이 식사하러 들어갈 때이다. 줄에 아무도 없는데 식사하러 들어오는 경우에 index error가 발생할 수 있지만, 문제에서 '식사 1인분이 준비될 때는 식당 입구에서 대기 중인 학생이 항상 존재한다'라는 문구가 존재하므로 우리는 마음놓고 pop을 사용할 수 있다!

for _ in range(n):
    info = list(map(int,input().split()))	#입력
    if len(info) == 1:	#입력이 2라면?
        stack.pop(0)	#식사가 준비되었으니 현재 대기줄 맨 앞에 있는 인원을 제거해준다
    else:	#아니라면 마지막에 줄을 세운다
        stack.append(info[1])

2. 문제에서 원하는 출력값 저장하기

현재 줄을 만들어 주었으므로, 이제 최대값을 갱신만 해주면 된다. 이때 '대기하는 학생 수가 최대인 경우가 여러 번이라면 맨 뒤에 줄 서 있는 학생의 번호가 가장 작은 경우를 출력한다.'라는 조건이 있으므로, 현재 줄의 인원이 최댓값과 같다면 마지막에 서있는 인원의 번호를 비교하여 작은값을 가져가 주면 된다!

if maxs[0] < len(stack):	#현재 줄에 최대 인원이 있다면 갱신해준다
        maxs[0] = len(stack)
        maxs[1] = stack[-1]
    elif maxs[0] == len(stack):	#현재 줄에 인원이 최대라면? 마지막 인원이 작은 값을 취해준다
        maxs[1] = min(maxs[1],stack[-1])

 

Code

input = __import__('sys').stdin.readline

n = int(input())
stack = []	#현재 대기줄
maxs = [0,0]
for _ in range(n):
    info = list(map(int,input().split()))	#입력
    if len(info) == 1:	#입력이 2라면?
        stack.pop(0)	#식사가 준비되었으니 현재 대기줄 맨 앞에 있는 인원을 제거해준다
    else:	#아니라면 마지막에 줄을 세운다
        stack.append(info[1])

    if maxs[0] < len(stack):	#현재 줄에 최대 인원이 있다면 갱신해준다
        maxs[0] = len(stack)
        maxs[1] = stack[-1]
    elif maxs[0] == len(stack):	#현재 줄에 인원이 최대라면? 마지막 인원이 작은 값을 취해준다
        maxs[1] = min(maxs[1],stack[-1])

print(maxs[0],maxs[1])