[BaekJoon] 백준 1620번 나는야 포켓몬 마스터 이다솜

[BaekJoon] 백준 1620번 나는야 포켓몬 마스터 이다솜

 

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

 

내코드

 

처음엔 무작정 배열에 넣어풀어봤다.

역시나 시간초과가 났다.

N, M 최대값이 100,000인데 python의 list 자료형에서 index 메서드의 시간 복잡도가 O(n)이라서 총 O(M*N)의 시간 복잡도가 나오기 때문인가보다. 1억당 1초라 하면 100,000 * 100,000를 게산하면 1억을 훌쩍 넘겨버린다.

# 틀린코드

N, M = map(int, input().split())
arr = ["" for _ in range(N)]

for i in range(N):
    arr[i] = input()

for _ in range(M):
    question = input()
    if question.isdigit():
        print(arr[int(question) - 1])
    else:
        print(arr.index(question) + 1)

index 메서드에서 시간이 오래 걸리는 것 같아서 포켓몬의 이름과 번호를 key-value로 저장할 수 있는 딕셔너리 형태도 추가로 사용해 보기로 했다.

+ sys.stdin.readlin으로 입력을 받을 때 개행문자도 같이들어가기 때문에 strip으로 제거해줘야한다.

# 맞은 코드

import sys

input = sys.stdin.readline
N, M = map(int, input().split())
arr = ["" for _ in range(N)]
dic = {}

for i in range(N):
    arr[i] = input().rstrip()
    dic[arr[i]] = i + 1

for _ in range(M):
    question = input().rstrip()
    if question.isdigit():
        print(arr[int(question) - 1])
    else:
        print(dic[question])