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

문제 링크

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

TISTORY

문제 풀이

---

 본 문제는 일반적인 배열로 풀게 될 경우 시간 초과가 나게 된다.
배열로 구현하게 되면 자료구조에 포켓몬의 이름과 도감 번호를 저장하고 그것을 검색해나가는 과정에서 시간이 초과된다. 최악의 경우를 살펴보자.
 포켓몬의 수인 N과 풀어야할 문제 M이 있다. 그리고 둘의 최댓값은 100,000이다. 둘 다 100,000이라고 가정해보자.
문제 M개가 전부 배열의 마지막 원소. 즉, 100,000번째 원소를 구하는 문제라고 하면 문제 하나를 풀 때 탐색 연산을 100,000번 진행하게 된다.
그런 문제를 M번 풀게 되면 100,000 * 100,000 번 연산을 진행하니 총 연산 횟수는 10,000,000,000(십억)번이다.
 1초에 약 1억번 정도의 연산을 하는 일반적인 컴퓨터의 연산 능력으로는 절대 1초안에 풀 수 없는 문제가 돼버린다.

그렇다면 다른 접근이 필요하다.

문제를 M번 푸는 경우는 개선할 방법이 없다. 그렇다면 탐색에서 시간을 단축해보자. 방법은 2가지가 있다.

1. 탐색 방법을 바꾸는 방법
2. 배열이 아닌 딕셔너리(해시 테이블)를 사용하는 방법

사실 이 문제는 2년전에 C++로 1번 방법을 사용해 풀었던 문제이다.
링크: https://www.acmicpc.net/source/18154796

로그인

퀵 소트와 이분 탐색 함수를 구현하여 풀었으나 푼 시기가 너무 오래되어 2번 방법으로 다시 풀어보았다.

해시 테이블이란?

 일단 해시 테이블을 알기 전에 파이썬의 자료구조인 dictionary 의 접근, 탐색, 멤버 연산의 실질적 소요 시간에 대한 글은 다음 링크를 참고해주길 바란다.https://towardsdatascience.com/faster-lookups-in-python-1d7503e9cd38

Faster Lookups In Python

 해시라는 것을 한 문장으로 표현하자면 '공간을 희생하여 시간을 얻는 자료구조'로 표현하고 싶다. 
해시 함수라는 함수를 네트워크 전공 시간에 언뜻 들었던 기억이 난다. 비밀번호와 같이 암호화 해야하는 내용을 해시 함수의 인자로 전달하면 그것에 일대일 대응되는 알 수 없는 데이터로 변하게 된다.
 해시 테이블은 그것을 자료구조화, 시각화한 것이라고 지금까지는 말할 수 있을 것 같다.
저장하고 싶은 데이터를 해시 함수에 인자로 전달해 얻어지는 값이 곧 주소값이 되기 때문에 배열(Linked List)과 같이 접근에 오랜 시간이 걸리지 않는다. 주소값에 직접 access하면 되니깐!

(이해에 용이한 아주 좋은 그림이 있어 첨부)

출처: https://fierycoding.tistory.com/68

문제 코드

딕셔너리 자료구조를 2개를 형성하여 해시 테이블의 특징인 빠른 접근으로 값을 출력한다.

input = __import__('sys').stdin.readline
n, m = map(int,input().split())

dict_by_num = dict()
dict_by_name = dict()

for i in range(n):
    name = input().rstrip()
    dict_by_num[i+1] = name
    dict_by_name[name] = i+1
    # key: number, value: name
    
for _ in range(m):
    tmp = input().rstrip()
    if 'A' <= tmp[0] <= 'Z':
        # 첫번째 문자가 알파벳 대문자일 경우 key를 출력
        print(dict_by_name[tmp])
    else:
        # 숫자가 들어왔을 경우 value를 출력
        print(dict_by_num[int(tmp)])