Baekjoon 7785.py [회사에 있는 사람]

hohooodo·2021년 7월 11일
0

Problem Solving

목록 보기
21/32
post-thumbnail

문제가 궁금하다면?

내 풀이

import sys
input = sys.stdin.readline
n = int(input())
arr = {}

for _ in range(n):
    name, state = input().split()
    if state == 'enter':
        arr[name] = 1
    else:
        arr[name] = 0

arr = sorted(arr.items(), key=lambda x: x[1])
arr = sorted(arr, reverse=True)

for i in arr:
    if i[1] > 0:
        print(i[0])

풀이 복기

문제를 처음 접했을때 스택을 사용해서 풀면 될거라고 생각했다. append(), remove()를 사용해서 구현했지만 시간초과로 통과하지못함.remove()의 시간복잡도가 O(n)이므로 불가.

출입 기록수가 2~10000000 인것을 그때서야 확인했다. 미리미리 확인했으면 스택을 사용하지 않고 다른 방법으로 풀었을것같다. 조건을 잘 확인하는 습관 필요함.

튜플을 정렬하는 과정에서 lambda식을 잘 사용하지 않았는데 익숙해질 필요를 느낌.

다른 풀이를 보며

set() 을 사용하면 remove()의 시간복잡도 O(1)로 사용가능하다. 이 방법으로 더 빠른풀이 가능. 마찬가지로 dict()를 가지고 풀어도 시간복잡도 O(1). 전에 많이 사용해봤다고 무조건 list 혹은 tuple로 손대지 말고, 시간복잡도를 고려해 최적의 해를 찾자.

profile
글을 잘쓰는 개발자가 되고싶습니다

0개의 댓글