백준 1620번: 나는야 포켓몬 마스터 이다솜 (S4) - Python 풀이

문제 설명

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

( 불필요하여 생략 )

네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네.

입력

첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어.

둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어. 아참! 일부 포켓몬은 마지막 문자만 대문자일 수도 있어. 포켓몬 이름의 최대 길이는 20, 최소 길이는 2야. 그 다음 줄부터 총 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어와. 문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 하고, 숫자로만 들어오면, 포켓몬 번호에 해당하는 문자를 출력해야해. 입력으로 들어오는 숫자는 반드시 1보다 크거나 같고, N보다 작거나 같고, 입력으로 들어오는 문자는 반드시 도감에 있는 포켓몬의 이름만 주어져. 그럼 화이팅!!!

출력

첫째 줄부터 차례대로 M개의 줄에 각각의 문제에 대한 답을 말해줬으면 좋겠어!!!. 입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하면 돼. 그럼 땡큐~

탐나긴 함

이게 오박사님이 나에게 새로 주시려고 하는 도감이야. 너무 가지고 싶다ㅠㅜ. 꼭 만점을 받아줬으면 좋겠어!! 파이팅!!!

예제 입력 1

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

예제 출력 1

Pikachu
26
Venusaur
16
14

풀이 과정

N개의 입력을 통해 포켓몬 도감을 완성하고, 이후의 M개의 입력에서 숫자가 뜨면 포켓몬 이름, 이름이 뜨면 포켓몬 번호를 출력하는 문제입니다.

우선 첫 번째로 제출한 코드는 시간 초과가 떴는데요.

N, M = map(int, input().split())
pokemon_dict = {}

for i in range(1, N+1):
    pokemon_dict[i] = input()

for _ in range(M):
    question = input()
    try:
        num = int(question)
        print(pokemon_dict[num])
    except:
        for k, v in pokemon_dict.items():
            if v == question:
                print(k)

번호를 key, 이름을 value로 하는 딕셔너리 형태로 도감을 만들었습니다. 입력이 숫자가 뜨면 key를 통해 바로 접근이 가능해서 value를 빠르게 출력할 수 있었지만, 입력이 이름이 뜨면 items 리스트에서 돌면서 해당 value를 가진 key를 찾는 과정이 필요했습니다. 아마 이 과정에서 시간이 오래 걸렸을 것으로 생각해서 이름을 key, 번호를 value로 가지는 딕셔너리를 생성해 총 2개의 딕셔너리를 사용하는 방식을 떠올렸습니다.

N, M = map(int, input().split())
pokemon_dict_name_key = {}
pokemon_dict_number_key = {}

for i in range(1, N+1):
    name = input()
    pokemon_dict_name_key[name] = i
    pokemon_dict_number_key[i] = name

for _ in range(M):
    question = input()
    try:
        num = int(question)
        print(pokemon_dict_number_key[num])
    except:
        print(pokemon_dict_name_key[question])

딕셔너리를 통한 key로 value에 접근하는 시간복잡도는 O(1)로 알고 있습니다. 그러나 해당 코드도 시간 초과가 뜬 거라면… 예외 처리 방식으로 구현한 try-except 부분을 제거해야겠다고 생각했습니다.

보니까 string 관련 함수 중에 문자열이 숫자로만 이루어져 있는지 판별하는 isdigit() 라는 메서드가 존재했습니다.

해당 메서드를 사용해 인풋이 숫자로만 이루어졌으면 key를 번호로 가지는 딕셔너리를 사용하고, 인풋이 숫자로 이루어진 게 아니라면 key를 이름으로 가지는 딕셔너리를 사용해 value를 출력했습니다.

정답 코드

# 입력
N, M = map(int, input().split())
# 이름을 key, 번호를 value로 가지는 딕셔너리
pokemon_dict_name_key = {}
# 번호를 key, 이름을 value로 가지는 딕셔너리
pokemon_dict_number_key = {}

# 입력 받아 각 딕셔너리를 구성
for i in range(1, N+1):
    name = input()
    pokemon_dict_name_key[name] = i
    pokemon_dict_number_key[i] = name

# 문제 M개
for _ in range(M):
    question = input()
    # 문제가 숫자로만 이루어진다면 포켓몬 번호를 가지고 포켓몬 이름을 묻는 것
    if question.isdigit():
        # 번호를 key로 가지는 딕셔너리에서 value 값 출력
        print(pokemon_dict_number_key[int(question)])
    # 문제가 숫자로만 이루어진 게 아니라면 포켓몬 이름을 가지고 번호를 묻는 것 
    else:
        # 이름을 key로 가지는 딕셔너리에서 value 값 출력
        print(pokemon_dict_name_key[question])

 

풀고난 후 궁금해서 2번째 코드와 마지막 정답 코드의 시간복잡도 차이점, 2번째 코드에서 시간초과를 일으키는 요소가 무엇인지 GPT에게 물어봤습니다.

답변 결과 >

좋아. 네가 준 두 코드는 기능적으로는 완전히 동일하지만, 시간 초과 여부는 미묘한 차이에서 갈린다.

그 핵심은 try-except에서 예외 발생 시의 성능 저하야.

---

✅ 두 코드의 구조적 시간복잡도 비교

요소 시간복잡도 (이론상)

N개의 포켓몬 저장	O(N)
M개의 질문 처리	O(1) per query
전체 질문 처리	O(M)
dict 접근 (조회)	O(1) 평균

따라서

두 코드 모두 이론적 전체 시간복잡도는 O(N + M)

(입력 처리까지 포함하면 O(N + M) 이상일 수 있음)

---

✅ 그런데 왜 첫 번째 코드는 시간 초과가 나올 수 있을까?

try:
    num = int(question)
    print(pokemon_dict_number_key[num])
except:
    print(pokemon_dict_name_key[question])

❗ 문제: except 블록이 너무 포괄적임

• except:는 모든 예외를 잡아버림 → KeyError, ValueError, TypeError 등 다 포함
• 만약 pokemon_dict_name_key[question]에서 KeyError가 발생하면 다시 except에 들어가고,
• 또 내부적으로 다시 예외가 나고, 그렇게 무한 루프 혹은 스택 트레이스를 길게 남기다가 터지는 거야.

📌 예외 발생 경로 (숨은 위험):

question = "abc"  # 숫자가 아닌 포켓몬 이름
→ int("abc") → ValueError → except 진입
→ print(pokemon_dict_name_key[question]) → KeyError (실수로 잘못된 이름이 들어온 경우)
→ 다시 except → 또 KeyError
→ 성능 저하 + 디버깅 난이도 + 시간 초과 위험

예외를 1번만 처리한다고 생각해도, 실제로는 2번 이상 발생하면 심각한 퍼포먼스 저하로 이어짐.

---

✅ 그럼 두 번째 코드가 왜 더 안정적이고 빠르냐?

if question.isdigit():
    print(pokemon_dict_number_key[int(question)])
else:
    print(pokemon_dict_name_key[question])

• 조건문 분기로 명확하게 흐름을 나눔
• 예외 발생 없음 → 모든 쿼리가 O(1)로 실행
• isdigit()은 문자열 검사일 뿐이고, 속도도 빠름 (O(k)이며, 일반적으로 매우 작음)

---

✅ 결론

비교 항목 try-except 방식 isdigit() 방식

예외 발생 시 성능	심각한 성능 저하 가능	없음
시간복잡도 (이론상)	O(M), 하지만 실행 시간 불안정	O(M), 안정적 O(1) per query
예외 원인 식별	어려움 (모든 예외 잡음)	명확한 분기 처리
시간 초과 위험	높음	거의 없음

---

✅ 추천: isdigit()을 사용하자.

---

 

이 답변 보고 except ValueError: 로도 바꿔서 제출해봤는데 이 경우도 시간 초과로 떴습니다. 이 문제와 같은 경우 예외 발생(= 인풋이 str)의 빈도가 높기 때문에 부적절한 방법이었던 것 같습니다. isdigit() 라는 효자 메서드가 있으니 이것을 사용합시다.

이상입니다.