(Python)백준 코딩테스트 연습 - 나는야 포켓몬 마스터 이다솜(1620)

1. 문제

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

1620번: 나는야 포켓몬 마스터 이다솜

2. 풀이

import sys
input = sys.stdin.readline

# n : 포켓몬 개수, k : 문제의 수
n, k = map(int, input().split())

# n_l : 포켓몬을 저장할 dict
n_l = {}
# re_n_l : key, value를 뒤집어 저장할 dict
re_n_l = {}
for i in range(n):
    profile = input().strip('\n')
    n_l[i+1] = profile
    re_n_l[profile] = i+1

for i in range(k):
    q = input().strip('\n')
    if q.isdigit():
        q = int(q)
        print(n_l[q])
    else:
        print(re_n_l[q])

3. 후기

 - 이 문제는 3번의 TypeError, 3번의 ValueError, 2번의 시간 초과 끝에 성공한 문제이다. 역시나 처음은 list 자료형을 사용하여 풀어보려 했지만, 하나의 값으로 list의 인덱스를 조회하는 것은 O(N)의 시간 복잡도를 갖게 되어 시간 초과가 된다. 때문에 dictionary 자료형을 사용하였고, value로 key를 확인하게 되면 시간 복잡도가 비효율적이게 되므로 index를 key로 갖는 dictionary와 포켓몬 이름을 key로 갖는 dictionary를 초기화하여 사용하였다.

 문제의 난이도가 올라갈 수록 알고리즘 내의 시간 복잡도를 계속해서 생각하게 되는데 문제를 풀게될 때 자료형으로 풀 수 있을지 없을지만 생각하는 것보다 시간 복잡도까지 생각하여 효율적인 코딩이 되었는가도 생각해보자.