[BOJ] 백준 1620번: 나는야 포켓몬 마스터 이다솜 (C++)

 

- 문제 출처 : https://www.acmicpc.net/problem/1620

---

1. 생각

신기한 제목과 내용의 문제이다. 하지만 새로운 자료구조인 map을 사용하는 문제이다.

 

map은 각 노드가 key, value 의 쌍으로 이루어진 트리의 자료구조이다.

set 처럼 중복을 허용하지 않으며, pair 객체로 저장되기에 first -> key, second -> value 로 대응된다.

(set과 비슷하지만 key값 기준 중복이 허용되지 않는 쌍으로 만들어지는 자료일 때, 사용하면 된다.)

따라서 선언 시에는 map <key type, value type> name 으로 하며,

set 과 동일하게 iterator를 통해 접근할 수 있다.

iterator를 통해 접근 시, iterator -> first, iterator -> second 로 각각 key, value에 접근이 가능하다. 

 

문제는 '포켓몬의 이름'이 N개 들어오고 이를 들어오는 순서대로 index를 매기며,

그 이후 M개의 이름 또는 숫자가 들어오면, 이름 -> 번호 / 번호 -> 이름 으로 대응해서 출력해주면 된다.

 

2. 난관 & 해결방법

#include <iostream>
#include <string>
#include <map>

 

이번에는 map을 include 해주고 시작하도록 한다.

 

우선 이 문제는 이름일 때 번호가 출력되고, 번호일 때는 이름이 출력되는 모습이다.

map은 key값을 통해서만 find를 이용해 접근할 수 있기에, 3가지 방법을 생각해보았다.

 

1. 이름으로 접근 시에는 find(), 숫자로 접근 시에는 iterator로 반복문 돌려 찾기 (또는 반대로)

: 이중 반복문으로 인해 시간초과 가능성이 있으므로 배제

2. map 과 reverse map을 만들기

: key value 값이 서로 반대로 저장되는 reverse map을 하나 더 만들어 각각 접근 시 활용

공간 복잡도는 더 높을 수 있으나, 접근 과정이 find로 동일하여 단순 구현이 쉬움.

3. map 과 string 배열 만들기

: 번호가 순차적으로 대응되기에, string 배열의 index만으로 접근이 가능함.

 

2, 3번 모두 구현해보기로 했다.

 

[ 2번 구현 ]

std::string name;
std::map <std::string, int> m;
std::map <int, std::string> m_rev;

 

우선 map과 reverse map의 초기화이다.

각각 반대로 key, value를 가지도록 지정해줬다.

따라서, 이름을 통해 번호를 찾고 싶으면 m, 번호를 통해 이름을 찾고 싶으면 m_rev를 이용.

 

for (int i = 1; i <= N; i ++)
{
    std::cin >> name;
    m.insert({name, i});
    m_rev.insert({i, name});
}

 

따라서 데이터를 insert할 때 각각 뒤집어서 insert해주면 된다.

 

for (int i = 0; i < M; i ++)
{
    std::cin >> name;
    if (name[0] >= '0' && name[0] <= '9')
        std::cout << m_rev.find(stoi(name)) -> second << "\n";
    else if ((name[0] >= 'A' && name[0] <= 'Z') || (name[0] >= 'a' && name[0] <= 'z'))
        std::cout << m.find(name) -> second << "\n";
}

 

그 후, 숫자로 들어온 값은 m_rev에 있는 key값을 통해 찾을 것이고,

이때는 입력된 name string을 int 형태로 바꿔서 찾아야하므로 stoi (string to int) 를 이용한다.

 

그리고 알파벳으로 들어온 값은 m에 있는 key값으로 찾으면 되고,

마찬가지로 찾은 iterator의 second에 접근하여 출력해준다.

 

[ 3번 구현 ]

std::string input;
std::string name[100001];
std::map <std::string, int> m;

 

이번에는 string 배열이다.

해당 배열에는 reverse map 에 담았듯이 문자열을 순차적으로 이름으로 저장해주면 된다.

 

for (int i = 1; i <= N; i ++)
{
    std::cin >> name[i];
    m.insert({name[i], i});
}

 

들어가는 입력 값이 바로 배열로 들어가면 되고, 해당 값을 map의 key로 쓰면 되어

훨씬 간결하고 이해하기 쉽게 작성되는 모습이다.

 

for (int i = 0; i < M; i ++)
{
    std::cin >> input;
    if (input[0] >= '0' && input[0] <= '9')
        std::cout << name[stoi(input)] << "\n";
    else if ((input[0] >= 'A' && input[0] <= 'Z') || (input[0] >= 'a' && input[0] <= 'z'))
        std::cout << m.find(input) -> second << "\n";
}

 

숫자가 들어오면 배열의 해당 인덱스를 찾아 이름을 출력해주면 된다.

그 외에는 모두 위와 같다.

 

확실히 군더더기 없이 필요한 컨테이너만 사용한 점이 좋은 것 같다.

 

3. 코드 및 결론

[ 전체 코드 ]

#include <iostream>
#include <string>
#include <map>

int main(void){
    int N, M;
    std::string input;
    std::string name[100001];
    std::map <std::string, int> m;
    std::cin.tie(NULL);
    std::ios::sync_with_stdio(false);
    std::cin >> N >> M;
    for (int i = 1; i <= N; i ++)
    {
        std::cin >> name[i];
        m.insert({name[i], i});
    }
    for (int i = 0; i < M; i ++)
    {
        std::cin >> input;
        if (input[0] >= '0' && input[0] <= '9')
            std::cout << name[stoi(input)] << "\n";
        else if ((input[0] >= 'A' && input[0] <= 'Z') || (input[0] >= 'a' && input[0] <= 'z'))
            std::cout << m.find(input) -> second << "\n";
    }
}

 

[ 결론 ]

 

두 방법으로 구현해보았는데, reverse map을 이용하는 것은 참신했지만

이 문제를 푸는데에 있어 최소한의 필요한 컨테이너만 충족하여 만들려면 string 배열을 이용하는 편이 더 좋은 것 같아

결론 코드에는 해당 방식으로 작성했다.

실제로 실행 시간에서도 조금의 차이는 있었으나, 크게 유의미하지는 않아 필요 시에 따라 적절히 컨테이너를 적용하면 될 것 같다.

 

앞으로 map을 언제 사용할지 파악하고, 잘 이용해보도록 하자.