[백준] 1620 나는야 포켓몬 마스터 이다솜 (실버4)

문제요약

나의 코드 및 설명 01 - 리스트 활용 (시간초과)

import sys

n, m = map(int, input().split())
lst = []
for _ in range(n):
    lst.append(sys.stdin.readline())

for _ in range(m):
    x = sys.stdin.readline()
    if 65<=ord(x[0])<=90 or 97<=ord(x[0])<=122:
        print(lst.index(x)+1)
    else:
        print(lst[int(x)-1])

나의 코드 및 설명 02 - 딕셔너리 활용 (for j in d.keys(): O(n)의 시간복잡도 -> 비효율적, 시간초과)

import sys

n, m = map(int, input().split())
d = {}
for i in range(1, n+1):
    d[i] = sys.stdin.readline().rstrip()

for _ in range(m):
    x = sys.stdin.readline()
    if 65<=ord(x[0])<=90 or 97<=ord(x[0])<=122: #영어이면
        for j in d.keys():
            if d[j] == x:
                print(j)
    else:
        print(d[int(x)])

나의 코드 및 설명 03 - 딕셔너리 활용 (문제해결)

import sys

n, m = map(int, input().split())
d_alpha = {} #알파벳을 값으로
d_num = {} #숫자를 값으로

for i in range(1, n+1):
    x = sys.stdin.readline().rstrip()
    d_alpha[i] = x
    d_num[x] = i

for j in range(m):
    y = sys.stdin.readline().rstrip()
    if 65<=ord(y[0])<=90 or 97<=ord(y[0])<=122: #영어이면
        print(d_num[y])
    else:
        print(d_alpha[int(y)])

다른 코드 및 설명 - 딕셔너리 한 번만 사용

import sys

n,m = map(int, input().split())
d = {}

for i in range(1, n+1):
    name = sys.stdin.readline().rstrip()
    d[name] = str(i)
    d[str(i)] = name

for i in range(m):
    x = input().rstrip()
    print(d[x])

피드백

처음에는 리스트를 활용하여 리스트 안에 찾으려는 값이 존재하는지 확인해보는 식으로 문제를 해결하려고 했으나 역시나 시간초과가 발생했다. 리스트에서 <in> 연산의 경우에는 O(n)의 시간복잡도가 발생하나, 딕셔너리를 활용하면 O(1)의 시간복잡도로 원하는 값을 찾을 수 있다. 하지만 나는 딕셔너리를 사용해놓고 시간복잡도 O(n)의 <for i in d.keys()> 코드를 작성하였다.(나의 코드 02) 

숫자와 알파벳을 키로 갖는 딕셔너리를 각각 두 개 생성해서 문제를 해결했으나, 하나의 딕셔너리에 키와 값을 반대로 집어 넣는 식으로 문제 해결도 가능하다. 

이번 문제를 통해 리스트와 딕셔너리 활용 시 주요 연산에 대한 시간복잡도를 비교할 수 있었고, 다음 번에 이번 문제와 같은 탐색 문제가 주어진다면 이분탐색과 더불어 딕셔너리를 활용하는 방법도 한 번 고민해보는 습관을 가져야겠다.