백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-1620 나는야 포켓몬 마스터 이다솜 편 (python)

문제 살펴보기!!

 

문제 링크 : https://www.acmicpc.net/problem/1620

반응형

솔루션 살펴보기!!

def main():
    import sys
    input = sys.stdin.readline
    pokemon = {}
    pokemon_seq = {}

    # 입력 처리
    N, Q = map(int, input().split())
    for i in range(1, N + 1):
        name = input().strip()
        idx = str(i)
        pokemon[name] = idx
        pokemon_seq[idx] = name

    # 질의 처리
    for _ in range(Q):
        query = input().strip()
        if query.isdigit():
            print(pokemon_seq[query])
        else:
            print(pokemon[query])

if __name__ == "__main__":
    main()

코드 흐름 및 풀이 전략

이 코드는 포켓몬 이름과 번호 간의 매핑을 이용하여 주어진 질의에 맞춰 포켓몬의 번호나 이름을 빠르게 찾아 출력하는 문제를 해결합니다. 문제 해결 흐름은 다음과 같습니다:

1. 입력 처리

• 먼저 포켓몬 이름과 번호를 입력받습니다. 포켓몬의 번호는 1부터 N까지 부여되며, 각각의 이름과 번호를 두 개의 dict에 저장합니다:
  • pokemon: 포켓몬 이름을 키로, 번호를 값으로 저장.
  • pokemon_seq: 번호를 키로, 포켓몬 이름을 값으로 저장.

이를 통해 이름을 입력하면 번호를, 번호를 입력하면 이름을 빠르게 찾을 수 있는 구조를 만듭니다.

2. 질의 처리

• 사용자가 포켓몬의 이름이나 번호로 질의를 하면, 입력값이 숫자인지 문자인지 확인합니다.
• 숫자인 경우에는 pokemon_seq에서 해당 번호에 대응하는 포켓몬 이름을 찾고, 문자인 경우에는 pokemon에서 해당 이름에 대응하는 번호를 찾습니다.
• 각 질의에 대해 빠르게 답을 출력할 수 있도록 사전(dict) 자료구조를 활용하여 평균 O(1)O(1)O(1)의 시간 복잡도로 질의에 답변할 수 있습니다.

3. 출력

• 질의의 결과를 즉시 출력합니다. 각 질의에 대해 사전에서 빠르게 값을 조회하고 그 값을 출력합니다.

 

주요 개념

1. 사전 자료구조 (Dictionary)
   • Python의 dict는 해시 테이블을 기반으로 한 자료구조로, 키-값 쌍을 저장하고 이를 매우 빠르게 조회할 수 있습니다.
   • 이 문제에서는 포켓몬의 이름과 번호를 빠르게 매핑하기 위해 두 개의 사전이 사용됩니다:
     • pokemon: 이름 → 번호
     • pokemon_seq: 번호 → 이름
   • 평균적으로 사전에서의 조회는 O(1)O(1)O(1)의 시간 복잡도를 가지므로, 많은 양의 데이터에 대해 빠르게 검색할 수 있습니다.
2. 빠른 입력 처리
   • 입력을 처리할 때 sys.stdin.readline()을 사용하여 대량의 입력을 빠르게 처리합니다. 이는 기본 input() 함수보다 성능이 우수하며, 특히 입력의 크기가 클 때 유리합니다.
   • strip()을 이용하여 입력된 문자열의 앞뒤 공백을 제거하고, 필요한 경우 isdigit()을 사용해 입력값이 숫자인지 문자인지 확인합니다.
3. 문자열과 숫자 변환 및 처리
   • 포켓몬의 번호는 자연수이므로, 이를 문자열로 변환하여 dict에 저장합니다. 문자열로 처리하면 번호와 이름 모두 동일하게 다룰 수 있습니다.
   • 사용자가 질의할 때 번호를 입력하면, isdigit()으로 이를 숫자 문자열로 판단하여 적절한 사전에서 포켓몬의 이름을 찾습니다.

728x90

최적화 전략

• 빠른 조회: 두 개의 사전(dict)을 활용해 이름 → 번호, 번호 → 이름 조회가 평균적으로 O(1)의 시간 복잡도를 가집니다. 이는 문제에서 요구하는 빠른 질의 처리에 적합한 자료구조입니다.
• 입력 최적화: sys.stdin.readline()을 사용하여 입력을 빠르게 처리하며, 이를 통해 대량의 입력에도 성능 저하 없이 문제를 해결할 수 있습니다.

예시 흐름

1. N=3, Q=3일 때:
   • 입력: 3 3
   • 포켓몬 이름:
     1. Pikachu → 저장: pokemon["Pikachu"] = "1", pokemon_seq["1"] = "Pikachu"
     2. Bulbasaur → 저장: pokemon["Bulbasaur"] = "2", pokemon_seq["2"] = "Bulbasaur"
     3. Charmander → 저장: pokemon["Charmander"] = "3", pokemon_seq["3"] = "Charmander"
2. 질의 처리:
   • 질의 1: "2" (숫자) → pokemon_seq["2"] = Bulbasaur
   • 질의 2: "Pikachu" (이름) → pokemon["Pikachu"] = 1
   • 질의 3: "Charmander" (이름) → pokemon["Charmander"] = 3

이러한 방식으로, 주어진 입력과 질의에 대해 빠르고 효율적으로 답을 구합니다.