7785 회사에 있는 사람 (python)

7785 회사에 있는 사람

문제 🌐

상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.

각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.

상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로글매을 작성하시오.

입력

첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.

회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.

출력

현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.

예제 입력

4
Baha enter
Askar enter
Baha leave
Artem enter

예제 출력

Askar
Artem

접근 방법

입력을 공백으로 구분하여 들어온 사람, 나간 사람을 체크하고 남은 사람을 사전 역순으로 출력하는 문제였다.

1. 동명이인은 없으며, 대소문자가 다르면 다른 이름이다.
   1. 하지만 여기서 생기는 궁금증: leave 하는 사람은 무조건 이전에 enter 한 사람인가? enter-leave 순서로 무조건 나오는 걸까? 만약 leave가 나왔는데 기존 직원이 없다면?

가장 먼저 떠오른 방법은 리스트 안에 “현재 회사에 있는 사람들” 의 이름을 append, remove 하는 방법. enter 시 append 하고 leave 시 remove 하면 성공할 거라 생각했다….

하지만 역시나 백준 난이도가 올라가면서 시간 초과 이슈가 발생했다. 게다가 수업 들으며 풀어서 잘못 쓴 부분이 있어 방금 다시 돌려 보았는데, 그대로 시간 초과 이슈!

리스트로 풀고자 했던 건 이거다.

N = int(input())
members = []
for _ in range(N):
    log = input().split()
    if log[1] == 'enter':
        members.append(log[0])
    else:
        if log[0] not in members:
            continue
        else:
            members.remove(log[0])
for member in sorted(members, reverse=True):
    print(member)

log를 log[0], log[1]로 구분하고 log[1] == ‘enter’ 라면 members 리스트에 log[0]을 append, log[1] == ‘leave’라면 members 리스트에서 log[0]을 remove 했다. 여기서 remove 탐색하는 과정이 시간이 오래 걸렸던 것 같다!

그래서 딕셔너리를 활용해 보았다.

members['이름'] = '상태'

이런 방식으로 선언하여 직원들의 상태를 관리하고, 사무실을 떠날 때 members에서 완전히 지워버리는 방식이다.

N = int(input())
members = {}
for _ in range(N):
    log = input().split()
    if log[1] == 'enter':
        members[log[0]] = 'enter'
    else:
        if members[log[0]]:
            del members[log[0]]

딕셔너리라는 자료형 특성상 순서가 없기 때문에 들어온 순서대로 출력하거나 하는 조건을 걸기 위해서는 리스트 같은 순서가 있는 자료형으로 구현해야 하는 것으로 보인다….

백준, 프로그래머스를 풀면서 난이도가 올라갈수록 시간 제한이나 효율성 검사가 점점 까다로워져서 알고리즘에 대한 공부를 확실히 해야겠다고 느꼈다. 더불어 자바와 파이썬 중 하나를 확실히 정해서 활용할 수 있는 라이브러리, 자료형 등에 익숙해져야겠다. (현실은 자바로 풀어야 하는데 외면하는 중…)

Full Solution

N = int(input())
members = {}
for _ in range(N):
    log = input().split()
    if log[1] == 'enter':
        members[log[0]] = 'enter'
    else:
        if members[log[0]]:
            del members[log[0]]
members = sorted(members, reverse=True)
for member in members:
    print(member)