[백준알고리즘] 1620번: 나는야 포켓몬 마스터 이다솜 -Python

[백준알고리즘] 1620번: 나는야 포켓몬 마스터 이다솜 -Python

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

1620번: 나는야 포켓몬 마스터 이다솜

문제가 굉장히 길다 ㅎㅎ;; 쭉 아래로 내려서 필요한 마지막 문단만 읽었다..

 

아무튼 이름으로 물어보면 번호를 대답하고, 번호로 물어보면 이름을 대답해야 한다.

 

두 가지 방법으로 풀었다.

하나는 딕셔너리를 이용해서 바로 맵핑해주는 것이다.

다른 하나는 실제로 이분 탐색을 적용한 방법이다.

 

첫 번째 딕셔너리를 이용한 방식은 간단하다. {name:id}, {id:name} 형식으로 하나의 포켓몬에 대해 두 번 입력해주면 된다.

 

두 번째 방법은 두 개의 리스트를 사용했다. 번호로 물어보는 경우를 대답하기 위해 일반 리스트에 저장을 한 방법과, 이름으로 물어본 경우를 대답하기 위해 리스트에 (name, id) 형태의 튜플로 저장해놨다.

(name, id)를 원소로 갖도록 저장한 리스트를 오름차순 정렬을 시켜준 뒤, 이름에 대해서 이분 탐색을 해주면 된다.

 

첫 번째 방법과 두 번째 방법 모두 파이썬이라서 간단하게 구현할 수 있었다. 딕셔너리를 이용한 방법이 속도가 더 빠르긴 했다.

import sys

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

quiz = list(sys.stdin.readline().rstrip() for _ in range(m))
for q in quiz:
    if q.isdigit():
        sys.stdout.write("{}\n".format(num2name[q]))
    else:
        sys.stdout.write("{}\n".format(name2num[q]))

import sys

n, m = map(int, sys.stdin.readline().split())
num2name = []
name2num = []
for i in range(n):
    t = sys.stdin.readline().rstrip()
    num2name.append(t)
    name2num.append((t, i+1))

name2num.sort()
quiz = [sys.stdin.readline().rstrip() for _ in range(m)]
for q in quiz:
    if q.isdigit():
        sys.stdout.write('{}\n'.format(num2name[int(q)-1]))
    else:
        lo, hi = 0, n-1
        while lo <= hi:
            mid = (lo + hi)//2
            if name2num[mid][0] == q:
                hi = mid
                break
            elif name2num[mid][0] > q:
                hi = mid-1
            else:
                lo = mid+1
        sys.stdout.write('{}\n'.format(name2num[hi][1]))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다