[python][백준] 10815 숫자카드, 1764 듣보잡, 1620 나는야 포켓몬 마스터 이다솜 (해시 문제)

[해시 깨달음]

1. 예상보다 내가 해시에 약한 거 같다 기본적인 알고리즘이기 때문에 더 기초를 탄탄하게 해야될 듯 하다
2. 해시를 사용하면 탐색에 O(1), 최악의 경우에도 O(N)이 걸리기 때문에 시간복잡도를 줄이고싶다면 잘 활용해야된다

 

1. 10815 숫자 카드 (https://www.acmicpc.net/problem/10815)

• 해시(딕셔너리)로 찾으면 시간 초과가 나지 않지만 for loop으로 찾게 되면 시간 초과가 남

n = int(input())
num_card = list(map(int, input().split()))
m = int(input())
is_have = {k:0 for k in list(map(int, input().split()))}

for n in num_card:
    if n in is_have.keys():
        is_have[n] = 1

for n in is_have.values():
    print(n, end=' ')

 

 

2. 1764 듣보잡 (https://www.acmicpc.net/problem/1764)

• 하나는 리스트 하나는 딕셔너리로 받아 탐색함

n, m = map(int, input().split())
notheard = {}
notseen = []
for _ in range(n):
    notheard[input()] = False

for _ in range(m):
    notseen.append(input())

count = 0
for s in notseen:
    if s in notheard.keys():
        count += 1
        notheard[s] = True

print(count)
for k, v in sorted(notheard.items()):
    if v == True:
        print(k)

 

 

3. 1620 나는야 포켓몬 마스터 이다솜 (https://www.acmicpc.net/problem/1620)

• 예상 외로 시간이 꽤 걸렸던 문제
• key = 포켓몬 이름, value = 고유 숫자 인 딕셔너리 하나와 key와 value가 반대인 딕셔너리를 하나 만들어 시간복잡도를 줄임
• value의 인덱스로 키를 찾아서 출력하면 시간 초과가 나게 됨
  • list(pokemon.keys())[list(pokemon.values()).index(int(x))]

시간 초과 코드

import sys

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

q = [sys.stdin.readline().rstrip() for _ in range(m)]

for x in q:
    if x.isdigit():
        print(list(pokemon.keys())[list(pokemon.values()).index(int(x))]) # 이 부분이 문제
    else:
        print(pokemon[x])

 

통과된 코드

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
pokemon = {}
rev_pokemon = {} # reverse dict를 만들어서 주어진 값이 문자열이던 숫자이던 hash 탐색 가능하게 만듬
for i in range(n):
    x = sys.stdin.readline().rstrip()
    pokemon[x] = i+1
    rev_pokemon[i+1] = x

for _ in range(m):
    x = sys.stdin.readline().rstrip()
    if x.isdigit():
        print(rev_pokemon[int(x)])
    else:
        print(pokemon[x])