[백준] 7785 회사에 있는 사람 (실버5) / 시간초과 해결, 리스트, 딕셔너리 시간복잡도

문제요약

나의 코드 및 설명 (시간초과)

• 리스트의 메서드인 append와 remove를 이용했으나 시간초과가 발생했다.

n = int(input())
ans = []
for _ in range(n):
    name, command = map(str, input().split())
    if command == 'enter':
        ans.append(name)
    elif command == 'leave':
        ans.remove(name)

ans.sort(reverse=True)

for i in ans:
    print(i)

다른 코드 및 설명

• 딕셔너리를 이용해 문제를 해결하였다.
• 리스트의 경우 원소를 제거할 때마다 O(n)의 시간복잡도가 발생하고, 최대 O(n^2)의 시간복잡도가 발생할 수 있다.
• 따라서, 원소의 추가와 제거의 시간복잡도가 O(1)에 해당하는 해시 맵, 딕셔너리를 이용해 문제를 풀어야 시간초과를 방지할 수 있다.

import sys

n = int(sys.stdin.readline())
dic = {}

for _ in range(n):
    name, command = map(str, sys.stdin.readline().split())
    dic[name] = command #딕셔너리에 key:name value:command 를 저장
    if command == "leave": #만약 value가 leave 라면
        del dic[name] #del dic[key]를 이용해 키를 제거

d = sorted(dic.items(), reverse = True) 
dic = dict(d)

for key in dic.keys():
    print(key)

 

딕셔너리 키 제거 방법 - del dict_name[key]

dic = {'국어': 99, '수학': 92, '과학': 100}
del dic['수학']

print(dic)

>> {'국어': 99, '과학': 100}

딕셔너리 키(key) 정렬 - sorted(dic.items(), reverse = True)

dic = {'apple': 2, 'banana': 3, 'coconut': 1}

d = sorted(dic.items(), reverse = True)

print(d) >> [('coconut', 1), ('banana', 3), ('apple', 2)] #리스트로 변환됨
print(dict(d)) >> {'coconut': 1, 'banana': 3, 'apple': 2}

딕셔너리 값(value) 정렬

• sorted() 함수의 매개변수에는 reverse 매개변수 뿐만 아니라, key 매개변수도 존재.
  key 매개변수 : 무엇을 기준으로 정렬하냐~ => key=lambda x: x[1] : value 기준으로 정렬 

dic = {'apple': 2, 'banana': 3, 'coconut': 1}

d = sorted(dic.items(), key=lambda x: x[1], reverse=True)
print(d) >> [('banana', 3), ('apple', 2), ('coconut', 1)]

print(dict(d)) >> {'banana': 3, 'apple': 2, 'coconut': 1}

피드백

이번 문제를 통해 리스트의 원소를 제거할 때의 시간복잡도가 O(n)인 것을 알 수 있었고, 딕셔너리 원소의 추가, 제거의 시간복잡도가 O(1)인 것을 알 수 있었다.