[1620] 나는야 포켓몬 마스터 이다솜

시간초과 코드

n,m = map(int, input().split())

pocketmons = []
finds = []


for i in range(n):
    temp = input()
    pocketmons.append(temp)

for i in range(m):
    temp = input()
    if temp.isdigit():
        print(pocketmons[int(temp)-1])
    else:
        print(pocketmons.index(temp)+1)

 

이유 : 리스트 조회를 하면 최악의 경우 100억회 조회. 제한 시간 2초임

index함수는 리스트 순회함 O(n^m)

조회 속도가 빠른 dict를 사용해야 함

dict는 조회 시 Hash를 사용함 O(1)

프로그램 전체 시간 복잡도는 O(N + M)

(출처: Gemini)

n,m = map(int, input().split())

num_to_name = {}
name_to_num = {}


for i in range(n):
    temp = input()
    num_to_name[i] = temp
    name_to_num[temp] = i

for i in range(m):
    temp = input()
    if temp.isdigit():
        print(num_to_name[int(temp)-1])
    else:
        print(name_to_num[temp]+1)