문제
여러 명의 학생이 식사하기 위하여 학교 식당을 향해 달려가고 있다. 학교 식당에 도착한 학생은 식당 입구에 줄을 서서 대기한다. 학교 식당에 먼저 도착한 학생이 나중에 도착한 학생보다 식당 입구의 앞쪽에서 대기한다. 식사는 1인분씩 준비된다. 식사 1인분이 준비되면 식당 입구의 맨 앞에서 대기 중인 학생 1명이 식당으로 들어가서 식사를 시작한다. 식사를 시작한 학생은 항상 식사를 마친다.
학생이 학교 식당에 도착하고 식사가 준비되는 n개의 정보가 저장된 A가 주어진다. A에 저장된 첫 번째 정보부터 n번째 정보까지 순서대로 처리한 다음, 식당 입구에 줄을 서서 대기하는 학생 수가 최대가 되었던 순간의 학생 수와 이때 식당 입구의 맨 뒤에 대기 중인 학생의 번호를 출력하자. 대기하는 학생 수가 최대인 경우가 여러 번이라면 맨 뒤에 줄 서 있는 학생의 번호가 가장 작은 경우를 출력하자.
A에 저장된 n개의 정보는 아래 두 가지 유형으로 구분된다. 첫 번째가 유형 1, 두 번째가 유형 2이다.
1 a: 학생 번호가 양의 정수 a인 학생 1명이 학교 식당에 도착하여 식당 입구의 맨 뒤에 줄을 서기 시작한다.
2: 식사 1인분이 준비되어 식당 입구의 맨 앞에서 대기 중인 학생 1명이 식사를 시작한다.
식사 1인분이 준비될 때는 식당 입구에서 대기 중인 학생이 항상 존재한다. 식당 입구에 줄을 서서 대기하였으나 식사가 준비 안 된 학생은 식사를 못 한다.
입력
첫 번째 줄에 n이 주어진다.
다음 줄부터 n개의 줄에 걸쳐 한 줄에 하나의 정보가 주어진다. 주어지는 정보는 유형 1, 2중 하나이다.
출력
첫 번째 정보부터 n번째 정보까지 순서대로 처리한 다음, 식당 입구에 줄을 서서 대기하는 학생 수가 최대가 되었던 순간의 학생 수와 이때 식당 입구의 맨 뒤에 대기 중인 학생의 번호를 빈칸을 사이에 두고 순서대로 출력한다. 대기하는 학생 수가 최대인 경우가 여러 번이라면 맨 뒤에 줄 서 있는 학생의 번호가 가장 작은 경우를 출력한다.
제한
- 1 ≤ n ≤ 100,000
- A에는 유형 1, 유형 2만 저장되어 있다.
- 1 ≤ a ≤ n, 모든 양의 정수 a의 값은 서로 다르다.
예제 입력 1
5
1 2
1 1
2
1 3
2예제 출력 1
2 1첫 번째 1 2를 처리한 후, 대기 줄은 2가 된다.
두 번째 1 1을 처리한 후, 대기 줄은 2 1이 된다. 대기줄 2 1은 2번 학생이 앞쪽, 1번 학생이 뒤쪽에서 대기 중임을 의미낸다.
세 번째 2를 처리한 후, 앞쪽에서 대기 중인 2번 학생이 대기 줄을 나와서 식사를 하므로 대기 줄은 1이 된다.
네 번째 1 3을 처리한 후, 대기 줄은 1 3이 된다.
다섯 번째 2를 처리한 후, 앞쪽에서 대기 중인 1번 학생이 대기 줄을 나와서 식사를 하므로 대기 줄은 3이 된다.
다섯 개의 정보를 처리하는 동안 대기 줄에 대기하는 학생 수의 최댓값은 2이다. 학생 수가 2인 대기 줄은 '2 1', '1 3' 두 가지이며, 맨 뒤에 줄 서 있는 학생 번호가 가장 작은 경우는 ‘2 1’이다.
최종 코드
import sys
from collections import deque
input = sys.stdin.read
data = input().split()
index = 0
n = int(data[index])
index += 1
queue = deque()
max_queue_lenth = 0
max_queue_last_student_number = 0
for _ in range(n) :
check_number = int(data[index])
if check_number == 1:
student_number = int(data[index+1])
queue.append(student_number)
index += 2
if len(queue) > max_queue_lenth:
max_queue_lenth = len(queue)
max_queue_last_student_number = student_number
elif len(queue) == max_queue_lenth:
max_queue_last_student_number = min(max_queue_last_student_number, student_number)
elif check_number == 2:
queue.popleft()
index += 1
print(max_queue_lenth, max_queue_last_student_number)코드 분석
import sys
from collections import deque
input = sys.stdin.read
data = input().split()
index = 0
n = int(data[index])
index += 1sys 라이브러리로 입력 값을 한번에 data로 넣은 후, 0index부터 시작해서 첫 n에는 0번째 인덱스, 그 이후 index+1 처리
queue = deque()
max_queue_lenth = 0
max_queue_last_student_number = 0헤깔릴 수 있는 부분은 가장 많은 대기줄이 있을 때, 맨 뒤의 학생의 숫자와 대기줄을 출력해야하는데, 가장 긴 대기줄이 여러개일 경우, 그 중에서 가장 작은 학생의 숫자를 뽑아내야 한다. 물론 맨 뒤에 있는 학생번호 중에
그래서 가장 대기줄이 길때를 max_queue_length에 그 당시 학생 숫자를 따로 변수로 처리해준다
for _ in range(n) :
check_number = int(data[index])
if check_number == 1:
student_number = int(data[index+1])
queue.append(student_number)
index += 2
if len(queue) > max_queue_lenth:
max_queue_lenth = len(queue)
max_queue_last_student_number = student_number
elif len(queue) == max_queue_lenth:
max_queue_last_student_number = min(max_queue_last_student_number, student_number)
elif check_number == 2:
queue.popleft()
index += 1
print(max_queue_lenth, max_queue_last_student_number)이 부분이 꽤 헤깔렸는데
일단 n만큼 반복하면서
각 줄에 첫번째 숫자가 1이면 학생의 번호가 뒤에 붙고, 2면 밥을 먹게 해주는 명령어 이므로, 그 번호를 체크하기 위해 check_number에 해당 숫자를 담아줬다.
그래서 1일 경우에는 그 뒤에 index+1에 있는 숫자가 학생숫자고, 그 값을 queue 즉, deque안에 넣어준다. 그다음에 1이였을 땐, 다음 인덱스는 +2를 적용,
queue의 길이가 제일 긴 대기줄보다 클 경우엔 그 값을 제일 긴 대기줄에 최신화하여 넣어줌으로써 대기줄의 최대값을 계속 갱신시켜준다. 그러면서 그 당시 들어간 가장 마지막 숫자를 max_queue_last_student_number에 넣어준다.
여기까진 나름 문제를 잘 해석했다면 이해할 수 있는 내용!!
elif 쪽은 파악해보면
그러다 가장 긴 대기줄이 같을 경우엔 맨 뒤의 학생 숫자가 작은 숫자를 뽑아내야하므로, 기존의 max_queue__last_student_number에 넣었던 값과 새로 반복문을 돌리면서 얻은 student_number의 값을 비교해서 더 적은 숫자를 새롭게 담아주면 된다. 그래야만 더 적은 숫자가 출력될 수 있는 로직이다.
이게 보면 쉽지만 머리로 떠올려서 구현하는건 아직 너무 어렵다 나에게..
그리고 이제 check_number가 2일땐 왼쪽부터 순서대로 밥먹으러 들어가는것이므로, popleft를 사용했다. 이것도 가능하기위해선 deque를 꼭 사용했어야 하는 문제였다.
