백준 1620번 [나는야 포켓몬 마스터 이다솜](C++) -yes6686- 티스토리

백준 문제 풀이: 1620 [나는야 포켓몬 마스터 이다솜]

---

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

문제 설명:

포켓몬 도감에서 이름으로 번호를 찾거나, 번호로 이름을 찾는 프로그램을 작성하세요.

입력 조건:

• 첫 번째 줄에 도감에 있는 포켓몬 수 N과 맞춰야 하는 문제의 개수 M이 주어집니다. (1 ≤ N, M ≤ 100,000)
• 다음 N줄에는 포켓몬의 이름이 순서대로 주어집니다. (1 ≤ 이름 길이 ≤ 20)
• 그 다음 M줄에는 포켓몬의 이름 또는 번호가 주어집니다.

출력 조건:

• M개의 줄에 문제의 정답을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <map>
#include <string>
using namespace std;

map<string, string> M; // 포켓몬 이름과 번호를 매핑

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    string s;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        M[s] = to_string(i); // 이름 -> 번호
        M[to_string(i)] = s; // 번호 -> 이름
    }

    string query;
    for (int i = 0; i < m; i++) {
        cin >> query;
        cout << M[query] << '\n'; // 매핑된 값 출력
    }

    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 `map` 자료구조를 사용하여 포켓몬 이름과 번호를 상호 매핑합니다. 문제를 빠르게 처리할 수 있습니다.

• 입력 처리:
  • `M[s] = to_string(i)`: 이름으로 번호를 찾을 수 있도록 저장합니다.
  • `M[to_string(i)] = s`: 번호로 이름을 찾을 수 있도록 저장합니다.
• 질의 처리:
  • `M[query]`를 사용하여 이름 또는 번호에 매핑된 값을 출력합니다.

시간 복잡도 분석:

• 포켓몬 등록: O(N).
• 질의 처리: O(M).
• 전체 시간 복잡도: O(N + M).

효율적으로 처리 가능합니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
5 5
Pikachu
Raichu
Charmander
Bulbasaur
Squirtle
1
Raichu
3
5
Pikachu

출력:
Pikachu
2
Charmander
Squirtle
1

주어진 입력에 따라 이름과 번호를 상호 참조하여 정확한 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!