[BOJ_Python] 13414. 수강신청

문제

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

 

사용 알고리즘

구현

 

풀이

고려사항

1. 이미 수강신청 대기에 있는 학생인지

 

후기

1. 처음에는 리스트를 만들어 remove와 append로 관리하였다.

현재 수강신청을 누른 학생이 이미 이전에 누른 이력이 있다면 리스트에서 제거 후

다시 맨 뒤에 넣어주는 방식을 선택했다.

2. 하지만 이 방식은 시간초과가 발생하였다.

- 학생이 있는지 확인하는 작업: 최악의 경우 O(N)

- 학생을 제거하는 작업: 최악의 경우 O(N)

- 학생을 추가하는 작업: O(1)

-> 따라서 전체 시간 복잡도는 O(N**2)

 

3. 때문에 딕셔너리를 활용한 방식으로 변경하였다.

딕셔너리를 들어온 순서로 갱신해주고

value를 기준으로 정렬 후 K개를 뽑아주는 방식을 선택하였다.

이때, 다시 들어온 값도 현재의 순서로 갱신되기때문에 따로 remove 작업이 필요없어진다.

4. 해당 방식은 시간복잡도를 더 효율적으로 관리할 수 있다.

- 각 학생 ID를 딕셔너리에 추가하는 작업: 각 N개의 입력에 대해 O(1)의 시간이 걸리므로 전체적으로 O(N)

- 딕셔너리 항목 정렬: O(Nlog⁡N)

- 첫 K개의 항목 출력: O(K)

-> 따라서 시간 복잡도는 O(Nlog⁡N)

 

5. 정리하면 

리스트의 remove와 in 검사 사용한 시간복잡도는 O(N**2)

딕셔너리와 정렬을 사용하는 시간복잡도는 O(Nlog⁡N)

 

코드

import sys

input = sys.stdin.readline

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

students = {}
for i in range(N):
    student = input().rstrip()
    students[student] = i

sort_students = sorted(students.items(), key=lambda x: x[1])

temp = 1
for key, value in sort_students:
    print(key)
    if temp == K:
        break
    temp += 1

 

시간초과 코드

import sys

input = sys.stdin.readline

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

q = []
for _ in range(N):
    student = input().rstrip()
    if student in q:
        q.remove(student)
    q.append(student)

for i in range(K):
    print(q[i])

 

결과