#12 [파이썬] 백준 7785번 문제: 회사에 있는 사람

<문제>

www.acmicpc.net/problem/7785

7785번: 회사에 있는 사람

---

 

<소스코드>

 

처음에 작성했던 "시간초과😂"가 난 코드는 아래와 같다.

import sys

n = int(input())
result = []

for i in range(n):
    name, check = map(str, sys.stdin.readline().split())
    if name not in result:
        result.append(name)
    else:
        result.remove(name)

result.sort(reverse=True)
for i in result:
    print(i)

 

(문제점) 시간초과가 난 이유는 containment연산자와 remove연산자 때문이다. containment연산은 x in I 또는 x not in l와 같이 포함여부를 확인하는 것이다. containment연산자의 시간 복잡도는 O(N)이다. 즉, 리스트 내의 원소가 많아질수록 많은 시간을 요구한다. remove연산은 l.remove(i)와 같이 리스트 내 특정 값을 지우는 것이다. 마찬가지로 O(N)의 시간 복잡도를 가지며 원소의 개수에 비례하게 시간이 늘어난다.

 

 

(해결책) containment연산으로 인한 시간초과 문제를 보완하기 위해 dictionary를 사용하여 사람이름과 enter/leave를 쌍으로 묶었다. l[i] = x는 Store(또는 Assignment)연산자라 칭하며 시간 복잡도는 O(1)이다. del l[i]와 같이 dictionary의 특정 key:value를 삭제하는 것을 Delete연산이라 하며 시간 복잡도는 O(1)이다. 따라서 리스트 내에서 사람이름을 추가하고 지우는 것보다 딕셔너리를 이용하여 추가하고 지우는 것이 훨씬 빠르다.

 

 

시간초과를 해결한 코드는 아래와 같다.

 

---

 

<NOTE>

1. 리스트와 딕셔너리 연산의 시간복잡도

	연산	시간 복잡도	연산	시간 복잡도
리스트	x in l 또는 x not in l	O(N)	l.remove(i)	O(1)
딕셔너리	l[i] = x	O(1)	del l[i]	O(1)

 

2. 리스트 내의 문자열 또는 숫자 정렬

문자열의 정렬은 알파벳 순서로 정렬하는 것을 의미한다. 정렬은 크게 sort()와 sorted()가 있는데, sort()는 기존의 리스트 자체를 바꾸는 것이고 sorted()는 새로운 변수를 할당하여 기존 리스트를 유지시키는 것이다.

a = [4, 3, 5, 7, 1]

a.sort()
print(a) #[1, 3, 4, 5, 7]

a = [apple, egg, milk, coke]

b = sorted(a)
print(b) #[apple, coke, egg, milk]

 

역순(내림차순)으로 정렬하고 싶을 때는 reverse=True라는 옵션을 사용할 수 있다.

a = [4, 3, 5, 7, 1]

a.sort(reverse=True)
print(a) #[7, 5, 4, 3, 1]

a = [apple, egg, milk, coke]

b = sorted(a, reverse=True)
print(b) #[milk, egg, coke, apple]