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

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

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

핵심 아이디어

• dictionary() -> 만약 리스트에서 탐색을 할 경우 시간복잡도는 O(n). 따라서 index를 탐색할 때, 데이터의 양에 따라 시간초과가 발생할 수 있기 때문에 자료구조별 시간 복잡도를 잘 생각해야 한다. 파이썬에서 딕셔너리는 hash table을 사용한 것으로, 데이터를 읽을 때 시간복잡도가 O(1)이다. 그러므로 인덱스 탐색이나 특정 문자 탐색을 할 때, dictionary를 사용하는 것이 유리할 수 있다.
• 문자열 key 입력 -> int value 반환, 정수 key 입력 -> 문자열 value 반환. 즉, 주어지는 내용을 dict에 key:value 형태로 번호:이름 또는 이름:번호로 한번씩 저장한 후에 그대로 찾아서 출력만 하면 되는 문제

(참고)리스트 vs 딕셔너리

• A list index is always of type integer -> 리스트는 인덱스가 항상 정수
• The index of dictrionary can be of any immutable type. -> 딕셔너리 인덱스는 변하지 않는 어떤 type도 가능. 또한 딕셔너리 키는 중복을 허용하지 않는다. must be unique.
• 딕셔너리: Key는 must be unique & imputable. Value는 can be any type(immutable & mutable) & can have duplicate
• The location of a value depends on the key only and it is determined from the key by a hash function. Also, The hash function is deterministic. Locations are not chosen randomly!

풀이

import sys
input = sys.stdin.readline

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

# 딕셔너리에 포켓몬 저장
# 번호: 이름
int_key = {} # 키 값이 int인 딕셔너리
# 이름: 번호
str_key = {} # 키 값이 문자열인 딕셔너리

for i in range(n):
	name = input().rstrip()
	# 입력받은 값이 문자열인 경우, 즉 key가 문자열
	str_key[name] = i
	# 입력받은 값이 숫자인 경우, 즉 key가 숫자
	int_key[i] = name

#print(int_key) {0: 'Bulbasaur\n', 1: 'Ivysaur\n', ... , 25: 'Raichu\n'}
#print(str_key) {'Bulbasaur\n': 0, 'Ivysaur\n': 1, ... , 'Raichu\n': 25}
# 따라서 rstrip()을 해주어야한다. 

#문제 받고 정답 출력하기
for _ in range(m):
	item = input().rstrip()
	# 만약 숫자를 입력받으면 키 값이 int 딕셔너리에서 value가져오기
	if item.isdigit() == True:
		print(int_key[int(item)-1])
	else: # 문자열을 입력받으면 문자열 딕셔너리에서 value가져오기
		print(str_key[item]+1)

처음에는 정답을 출력할 때 int_key[int(item)-1], str_key[name]+1 처럼 +1, -1 해주는 부분이 풀 때마다 헷갈려서 아예 처음부터 인덱스를 0이 아닌 1부터 시작하도록 다시 풀었습니다. 그렇게 해주면 마지막 출려 할 때 +/- 1을 해주지 않아도 됩니다.

import sys
input = sys.stdin.readline

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


# key가 int -> str value 반환
int_key = {}
# key가 str -> int value 반환
str_key = {}

for i in range(1,n+1):
	name = input().rstrip()
	# 딕셔너리 초기화
	int_key[i] = name
	str_key[name] = i
for i in range(m):
	s = input().rstrip()
	if s.isdigit():
		# 입력값이 숫자이면
		print(int_key[int(s)])
	else:
		print(str_key[s])