[백준/Python] 7785번 회사에 있는 사람

---

문제

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

---

문제 이해

이 문제는 입력값에 enter가 들어가면 리스트에 삽입하고 입력값에 leave가 들어가면 리스트에서 제거하는 문제이다.

입력값을 띄어쓰기를 기준으로 나눠준 후, 기준에 따라 리스트에 삽입과 제거를 한다. 그리고 사전 역순으로 정렬해 주면 된다.

---

문제 풀이(시간 초과)

# 시간 초과

n = int(input())

li = []

for _ in range(n):

    people = input()

    ps = people.split()

    if ps[-1] == 'enter':

        li.append(ps[0])

    elif ps[-1] == 'leave':

        li.remove(ps[0])

# 정렬

li = sorted(li)[::-1]

for i in li:

    print(i)

 

li라는 리스트를 만든 후, 문제를 풀어보니 시간초과가 되었다.

'li.append(ps[0])'는 리스트에서 특정 값을 찾아 삭제하는 연산인데 이 과정에서 시간초과가 발생한 것이다.

시간초과를 해결하기 위해 리스트 대신 set()을 사용해서 풀어보았다.

 

List vs Set 시간복잡도

List의 시간복잡도는 O(n), Set의 시간복잡도는 O(1)이다.

 

Set이 효율적인 이유는 파이썬에서는 Set가 해시 함수와 해시 테이블로 구현되어 있기 때문이다.

 

해시란?

• 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것

 

따라서, Set은 해시 테이블 덕분에 데이터를 빠르게 검색, 삽입, 삭제를 할 수 있어서 효율적인 자료구조이다.

반면 List는 순차적으로 값을 찾기 때문에 시간이 오래걸리는 자료구조이다.

즉, List보다 Set이 시간복잡도가 빠르다.

---

문제 풀이(정답) 

# 정답 : remove() 사용

n = int(input())

li = set()

for _ in range(n):

    people = input()

    ps = people.split()

    if ps[-1] == 'enter':

        li.add(ps[0])

    elif ps[-1] == 'leave':

        li.remove(ps[0])

        # li.discard(ps[0])

 

# 정렬

li = sorted(li)[::-1]

for i in li:

    print(i)

 

Set()에서는 append()함수를 사용하지 못하므로 데이터를 추가할 때 append() 대신 add()를 사용해 주었다.

삭제할 때는 remove()와 discard()를 이용할 수 있는데 2가지 함수에는 차이점이 존재한다.

remove() vs discard()

remove() : 반드시 삭제해야 하는 값이 존재하는 것이 보장될 때 사용

discard() : 값이 존재할 수도 있고, 없을 수도 있는 경우 사용

 

이 문제의 경우에는 2가지 경우 모두 사용 가능하다.

 

블로그를 작성하며, Set()의 개념에 대해 더 확실하게 알게되었다.