초고

import sys
n, m = map(int,sys.stdin.readline().strip().split())
poket = {}
ans = []
for i in range(1,n+1):
    poket[i] = sys.stdin.readline().strip()
for i in range(m):
    quiz = sys.stdin.readline().strip()
    if quiz.isdigit():
        ans.append(poket[int(quiz)]+'\n')
    else:
        for key, value in poket.items():
            if value == quiz:
                ans.append(str(key)+'\n')
print(''.join(ans))

• 딕셔너리를 이용해 다 저장하고 for 문을 돌면서 key, value 에 해당하는 값을 찾으려고 했다.
  => 시간초과ㅜ

시간복잡도는 O(N + M * N)

N개의 포켓몬을 사전에 저장하는 데 O(N)
M개의 질문 처리에 O(M * N)
모든 질문을 for문으로 검색해야할수도 있어서...

개선된 코드

import sys
n, m = map(int,sys.stdin.readline().strip().split())
poket_index = {}
poket_name = {}
ans = []
for i in range(1,n+1):
    name = sys.stdin.readline().strip()
    poket_index[i] = name
    poket_name[name] = i
for i in range(m):
    quiz = sys.stdin.readline().strip()
    if quiz.isdigit(): #숫자로 물어봤으면
        ans.append(poket_index[int(quiz)]+'\n')
    else: # 이름으로 물어봤으면
        ans.append(str(poket_name[quiz])+'\n')
print(''.join(ans))

수정사항

초고에 있는 코드는 value로 key를 찾기위해 시간을 많이 소요한다.

그래서 딕셔너리를 두개를 만들어 이를 해결했다.

시간 복잡도는 O(N + M)

N개의 포켓몬 이름을 사전에 저장하는 데 O(N)
M개의 질문을 처리하는 데 O(M)

따라서 O(N+M) 이 걸린다