[BOJ] 수강신청 (#13414)

 

 

문제 

 

국민대학교에서는 매 학기 시작 전 종합정보시스템에서 수강신청을 한다. 매 수강신청마다 아주 많은 학생들이 몰려 서버에 많은 부하가 가기 때문에, 국민대학교에서는 수강신청 부하 관리 시스템을 도입하기로 결정하였다. 새로운 관리 시스템은 다음과 같은 방식으로 동작한다.

1. 수강신청 버튼이 활성화 된 후, 수강신청 버튼을 조금이라도 빨리 누른 학생이 대기목록에 먼저 들어간다.
2. 이미 대기열에 들어가 있는 상태에서 다시 수강신청 버튼을 누를 경우 대기목록의 맨 뒤로 밀려난다.
3. 잠시 후 수강신청 버튼이 비활성화 되면, 대기목록에서 가장 앞에 있는 학생부터 자동으로 수강신청이 완료되며, 수강 가능 인원이 꽉 찰 경우 나머지 대기목록은 무시하고 수강신청을 종료한다.

위의 표는 최대 수강 가능 인원이 3명인 알고리즘 수업에 대해 6명의 학생이 수강신청을 진행한 모습이다. 버튼이 비활성화 된 후, 먼저 규칙 1을 적용하여 클릭을 2번 이상 한 학생의 중복된 대기목록을 삭제한다. 중복된 목록을 제거한 후, 맨 앞에서부터 최대 수강 가능 인원인 3명을 선정한다. 표의 맨 오른쪽에는 그 최종결과를 나타낸 모습이다. 이와 같은 방법을 이용하여 최종적으로 수강신청에 성공한 인원을 출력하는 프로그램을 작성하시오.

 

 

나의 코드 

import sys

std, t = map(int,sys.stdin.readline().strip().split())
arr = [sys.stdin.readline().strip() for _ in range(t)]
step1 = []
step2 = []

# step1. 두번 이상 버튼 누른 사람 배열 맨 뒤로 보내기 
arr = arr[::-1]
for i in arr:
  step1.append(i)
  if i in step1[:len(step1)-1]:
    step1.pop()
step1 = step1[::-1]
  
# step2. 수강인원에 맞춰 수강생 뽑기
# 1. 수강인원보다 수강생이 많거나 같을 경우 
if len(step1) >= std:
  answer = step1[0:std]
# 2. 수강인원보다 수강생이 적은 경우 
if len(step1) < std:
  answer = step1

for k in answer:
  print(k)

분석 > 문제를 보고 리스트를 이용해 구현했지만, 시간초과가 떴다. 이 문제는 리스트를 사용하면 안되었다. 

 

 

해설 코드 

import sys

input = sys.stdin.readline

K, L = map(int, input().split())

queue_list = {}

for i in range(L):
    studentId = input().rstrip()
    queue_list[studentId] = i

cnt = 0
for x in sorted(queue_list.items(), key=lambda x: x[1]):
    cnt += 1
    if cnt > K:
        break
    print(x[0])

분석 > 해시맵을 사용하여 중복을 제거해주었다. 정말 경이로운 방법이다. 정렬을 할 때는 x[1]을 기준으로 해서 숫자가 작은 순서대로 정렬을 하고 제한된 수강인원 수대로 print를 해주면 되었다. 

 

해시 

dict = {}
arr = ['apple','apple','blueberry']

for i in range(len(arr)):
  dict[arr[i]] = i
print(dict) # {'apple': 1, 'blueberry': 2}

 

 

 

13414번: 수강신청