[python][백준/BOJ] 1620번 : 나는야 포켓몬 마스터 이다솜

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

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

 

✅ 첫 번째 시도

• 도감 내용을 리스트에 저장하고
• m만큼 반복문을 돌면서 들어오는 문제에 대해서 만약 숫자라면 l리스트[tmp-1] 값을 출력하고 
• 만약 문제가 문자열이라면 l리스트에서 index()를 활용하여 인덱스 값+1을 출력한다고 접근함.

import sys

n,m=map(int,sys.stdin.readline().split())
l=[]
for i in range(n):
    l.append(sys.stdin.readline().strip())

for i in range(m):
    tmp=sys.stdin.readline().strip()
    if tmp.isdigit() :
        print(l[int(tmp)-1])
    else:
        print(l.index(tmp)+1)

❗  .index() 사용으로 시간초과가 나왔을 것이라 판단함

❗ dict() 를 활용하자!

❗ index()의 시간복잡도는 O(N)이고, 딕셔너리 탐색 연산은 O(1)이므로 활용을 잘해보자~ ❗

 

✅ 두 번째 시도

• l을 리스트 대신 딕셔너리로 설정하고 반복문을 도는 인덱스인 i를 key, 도감내용을 value로 받았다.
• m만큼 반복문을 돌면서 들어오는 문제에 대해서 만약 숫자라면 l딕셔너리[tmp-1] 값을 출력하고
• 만약 문제가 문자열이라면 l딕셔너리에서 items()를 이용해 key 와 value값을 다 가져오고
• 조건문을 이용해 문제와 동일한 value값의 key값을 출력하고자 접근함.

import sys

n,m=map(int,sys.stdin.readline().split())
l=dict()
for i in range(n):
    tmp=sys.stdin.readline().strip()
    l[i]=tmp
print(l)

for i in range(m):
    tmp=sys.stdin.readline().strip()
    if tmp.isdigit() :
        print(l[int(tmp)-1])
    else:
        for k,v in l.items():
            if v==tmp:
                print(k+1)

❗ 출력 초과는 처음보는데 후ㅠㅠ 찾아보니 프로그램이 너무 많은 출력을 하는 경우에 발생한다고 한다. 

❗ 미리 구해놓은 정답 파일의 크기의 2배를 넘어가면 이 결과를 받는다. (틀렸습니다와 동일함 ㅎㅎ )

 

✅ 최종코드 

• 찾아보니 딕셔너리의 key와 value 값을 서로 바꾸어서 저장하는 방법이 있었다 !

# 딕셔너리 key와 value값 서로 바꾸기 문법

dict(map(reversed,값을 바꿀 딕셔너리.items()))

import sys

n,m=map(int,sys.stdin.readline().split())
l=dict()
for i in range(n):
    tmp=sys.stdin.readline().strip()
    l[i]=tmp

reverse_l =dict(map(reversed,l.items()))

for i in range(m):
    tmp=sys.stdin.readline().strip()
    if tmp.isdigit() :
        print(l[int(tmp)-1])
    else:
        print(reverse_l[tmp]+1)

 

✅ 딕셔너리 l과 reverse한 값인 reverse_l을 비교해보면 key와 value가 잘 바뀌어서 저장된 것을 볼 수 있다.