1620번: 나는야 포켓몬 마스터 이다솜 (acmicpc.net)

##


##
import sys
input = sys.stdin.readlines
l = list(map(lambda x:x.rstrip().replace('\x1a',''),input()))

N,M = map(int,l[0].split())
l2 = [0] + l[1:N+1]
query = l[-1*M:]

d = {}
for tmp in range(len(l2)):
    d[str(tmp)] = l2[tmp]

d_rev = {}
for k,v in d.items():
    d_rev[v] = k

for tmp in query:
    if tmp in d_rev:
        print(d_rev[tmp])
    else:
        print(d[tmp])
제출한 코드

아래서 4번째 줄에서 if tmp in l2:
이렇게 tmp를 리스트에서 찾으면 시간복잡도가 O(n)
dictionary 이용해서 이 부분이 O(1)되도록 해야한다. 


import sys
input = sys.stdin.read
l = input().splitlines()
l[-1] = l[-1].replace('\x1a','')

N,M = map(int,l[0].split())
l2 = l[1:N+1]
query = l[-M:]

d = {l2[i]:str(i+1) for i in range(N)} #이름:번호
d_rev = {v:k for k,v in d.items()} # 번호:이름

for tmp in query:
    if tmp in d.keys(): # 키에 이름이 있다면
        print(d[tmp])
    else:
        print(d_rev[tmp])
input().splitlines() 사용, ditcionary 부분 깔끔하게 바꾼것
근데 이 방법도 마지막 문자는 없애줘야 한다.