[백준][python] 1620번: 나는야 포켓몬 마스터 이다솜
1620번: 나는야 포켓몬 마스터 이다솜
문제
(생략)
오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라.
일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나,
포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라.
나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네.
입력 조건
둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와.
포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음… 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어.
아참! 일부 포켓몬은 마지막 문자만 대문자일 수도 있어.
포켓몬 이름의 최대 길이는 20, 최소 길이는 2야. 그 다음 줄부터 총 M개의 줄에 내가 맞춰야 하는 문제가 입력으로 들어와.
출력 조건
입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을,
문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하면 된다.
첫 번째 시도 . (2020년 2월 19일)
import sys
input=sys.stdin.readline
n,m = map(int,input().rstrip().split())
index = [str(i) for i in range(1,n+1)]
pocketmon=[]
for i in range(n):
pocketmon.append(input().rstrip())
for i in range(m):
x = input().rstrip()
if x in index:
print(pocketmon[int(x)-1])
else:
print(pocketmon.index(x)+1)
»intput
26 5
Bulbasaur
Ivysaur
Venusaur
Charmander
Charmeleon
Charizard
Squirtle
Wartortle
Blastoise
Caterpie
Metapod
Butterfree
Weedle
Kakuna
Beedrill
Pidgey
Pidgeotto
Pidgeot
Rattata
Raticate
Spearow
Fearow
Ekans
Arbok
Pikachu
Raichu
25
Raichu
3
Pidgey
Kakuna
»output
Pikachu
26
Venusaur
16
14
fail(시간 초과)
🌝 Thinking
[아이디어]
- 포켓몬을 리스트에 차례로 집어넣는다. 자료의 인덱스(index+1)가 포켓몬의 번호가 된다.
- 입력값이 인덱스에 해당하는 값이면 리스트에서 바로 포켓몬을 바로 찾아서 출력한다.
- 입력값이 포켓몬(Value)라면 리스트 내장함수의 .index()를 이용하여 해당 포켓몬의 인덱스를 출력한다.
두 번째 시도 . (2020년 3월 1일)
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
pocketmon = [ input() for i in range(n)]
dic={i+1 :pocketmon[i] for i in range(n)}
def key(val):
for i,j in dic.items():
if j == val:
return i
for i in range(m):
cmd = input().rstrip()
if cmd.isdigit():
print(dic[int(cmd)])
else:
print(key(cmd))
»intput
26 5
Bulbasaur
Ivysaur
Venusaur
Charmander
Charmeleon
Charizard
Squirtle
Wartortle
Blastoise
Caterpie
Metapod
Butterfree
Weedle
Kakuna
Beedrill
Pidgey
Pidgeotto
Pidgeot
Rattata
Raticate
Spearow
Fearow
Ekans
Arbok
Pikachu
Raichu
25
Raichu
3
Pidgey
Kakuna
»output
Pikachu
26
Venusaur
16
14
fail(시간 초과)
🌝 Thinking
조금 더 빠른 성능을 위하여 해시 문제에 걸맞는 딕셔러리 자료형을 이용하였다.
딕셔너리 자료형에서는 key값을 넣으면 value를 출력한다. 하지만 그 반대는 따른 구현이 필요하다.
그래서 key라는 함수를 만들었다.(val를 입력받아 일치하는 value가 나타나면 그 값의 key를 리턴)
[아이디어]
- 딕셔너리 자료형 key에 포켓몬 번호를 value에 포켓몬 이름을 넣는다.
- value값을 입력했을 때 key값을 찾아주는 함수를 구현한다.
- .isdigit()함수를 이용하여 명령을 구분하여 적절한 값을 출력한다.
이 또한 시간초과…
세 번째 시도 . (2020년 3월 1일)
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
dict={}
for i in range(n):
pocketmon = input().rstrip()
dict[i+1] = pocketmon
dict[pocketmon] = i+1
for i in range(m):
cmd = input().rstrip()
if cmd.isdigit():
print(dict[int(cmd)])
else:
print(dict[cmd])
»intput
26 5
Bulbasaur
Ivysaur
Venusaur
Charmander
Charmeleon
Charizard
Squirtle
Wartortle
Blastoise
Caterpie
Metapod
Butterfree
Weedle
Kakuna
Beedrill
Pidgey
Pidgeotto
Pidgeot
Rattata
Raticate
Spearow
Fearow
Ekans
Arbok
Pikachu
Raichu
25
Raichu
3
Pidgey
Kakuna
»output
Pikachu
26
Venusaur
16
14
success
🌝 Thinking
두 번째 풀이방법에서 value에 해당하는 key값을 찾으려면 딕셔너리를 순회를 해야했다.
이러한 과정이 시간 초과를 유발한다 생각하여 메모리를 조금 더 사용하더라도
key 값과 value값을 위치를 바꾼 자료 또한 딕셔너리에 추가해주었다.
(딕셔너리의 메모리할당량이 2배가 되었지만 속도는 엄청나게 빨라졌으리라 생각한다. )
💡 깨달은 점.
- .isdigit()은 문자열이 숫자로 구성되어 있는지 판별 해주는 함수이다.
- 나도 모르게 사용하는 for 구문이 시간복잡도를 상당히 증가시킬 수 있음을 알게 되었다.
댓글남기기