[BOJ 7785] 회사에 있는 사람 (Python)

들어가며

이 문제는 백준 단계별로 풀어보기에서 집합과 맵에 속한 3번째 문제이다.

문제 요약

회사의 출입 로그를 통해 회사에 있는 모든 사람을 출력하는 문제
입력 :
'출입 기록의 수 n'
'이름' 'enter or leave' 형식으로 n번 반복
출력 :
'회사에 있는 사람의 이름' 을 역순으로 한 줄에 한 명씩 출력

풀이

이 문제에서 주목해야 할 점은 2가지이다.
1. 출입 기록의 수는 $10^6$ 까지 주어진다.
2. 사전 순의 역순으로 한 줄에 한 명씩 출력한다.

출입 기록의 수가 $10^6$까지 가능하므로 list 대신 set을 써야한다.
(list의 delete 시간복잡도는 $O(N)$이다)

---

N = int(input())
log = set()
for i in range(N):
    name, commute = input().split()
    if commute == 'enter':
        log.add(name)
    elif commute == 'leave':
        log.remove(name)

위 예제 입력을 받는 형식과 enter, leave에 따라 set에 add()와 remove()를 하는 코드를 짜면 다음과 같다.

set의 원소 추가, 삭제 메서드
추가 : add()
삭제 : remove()

---

이제 log라는 set에 있는 멤버들을 사전 순의 역순으로 출력해야 한다.
set 자료형으로는 파이썬의 sort() 함수를 사용할 수 없으므로 list로 변환한 뒤 역순으로 정렬해야 한다.

log_list = list(log)
log_list.sort(reverse=True)

리스트 정렬
list.sort() : list를 정렬해준다. (반환값 None)
sorted(list) : 정렬된 list를 반환해준다. (반환값 list)
list.sort(reverse=True) : list를 역순으로 정렬해준다. (반환값 None)

---

이제 for문으로 출력 형식에 맞게 출력하면 끝이다.

for employee in log_list:
    print(employee)

...사실 끝이 아니다
위 코드를 그대로 조합해서 제출하면 시간초과가 나온다.

(한 번 틀린건 사전 순의 역순으로 출력하는 것을 빼먹었다...)

파이썬의 input() 함수는 시간을 많이 잡아먹기 때문에 여러 줄의 입력을 받는다면 sys.stdin.readline()을 써야한다.
자세한 정보는 이 글에서 참고하자.

import sys
input = sys.stdin.readline

위 코드를 맨 위에 적어주면 평소처럼 input으로 써도 무방하다.

백준에서 여러 줄을 입력받는 상황에서 써야할 코드

import sys
input = sys.stdin.readline

결과 코드

import sys
input = sys.stdin.readline

N = int(input())
log = set()
for i in range(N):
    name, commute = input().split()
    if commute == 'enter':
        log.add(name)
    elif commute == 'leave':
        log.remove(name)
        
log_list = list(log)
log_list.sort(reverse=True)
for employee in log_list:
    print(employee)

마치며

오랜만에 백준을 풀어봤더니 백준문제를 풀 때 입출력 형식을 잘 읽어야 한다는 점과 sys.stdin.readline을 써야한다는 여러 팁들을 까먹어서 조금 헤맸던 것 같다.

앞으로 백준 문제 푼 것들을 velog에 올리면서 각종 알고리즘 문제를 풀 때 알아야 하는 점들을 정리해가며 공부할 것이다. 😀