[BaekJoon 1620][⚪4] 나는야 포켓몬 마스터 이다솜

❓ 문제

백준 1620 - “나는야 포켓몬 마스터 이다솜”

🎯 난이도

Silver ⚪4

🧠 풀이

1. 내 풀이 (동적 배열 + 해시 맵)

- 알고리즘

• Data Structure, Set & Map, Hashing

- 설명

vector, unordered_map을 사용하는 풀이이다.

string을 저장하는 vector를 만들어 번호를 인덱스로 받아 이름을 저장하고, 키가 string, 값이 int인 unordered_map으로 이름을 받아 번호로 저장하는 방식이다.

이렇게 한 이유는, vector의 좋은 캐시 친화성과 인덱스 기반의 빠른 임의 접근, unordered_map의 해싱 기반 노드로의 빠른 임의 접근을 최대한 활용하기 위해서이다.

추가적으로 입력이 숫자임을 판별하는 함수를 isdigit을 활용해 만들었다. 앞으로도 써먹으면 좋은 로직이다.

vector와 unordered_map의 삽입, 탐색은 모두 O(1)이므로 전체적인 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>

#include <unordered_map>

#include <string>


using namespace std;

// 숫자임을 판별해주는 함수
bool IsNumber(const string& strInput)
{
    if(strInput.empty())
    {
        return false;
    }

    for(char chInput : strInput)
    {
        if(!isdigit(static_cast<unsigned char>(chInput)))
        {
            return false;
        }
    }
    
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{}, iM{};
    cin >> iN >> iM;

    vector<string> vecNum(iN + 1);  // 숫자를 인덱스로 이름을 저장하는 벡터
    unordered_map<string, int> umapString{};    // 이름을 인덱스로 숫자를 저장한느 벡터

    umapString.max_load_factor(0.7f);
    umapString.reserve(iN * 2);

    for(int i = 1; i <= iN; ++i)
    {
        string strName{};

        cin >> strName;

        vecNum[i] = strName;
        umapString[strName] = i;
    }

    while(iM--)
    {
        string strInput{};
        cin >> strInput;

        // 숫자면 이름으로 출력
        if(IsNumber(strInput))
        {
            cout << vecNum[stoi(strInput)] << '\n';
        }
        // 이름이면 숫자로 출력
        else
        {
            cout << umapString[strInput] << '\n';
        }
    }

    return 0;
}

---

💭 후기

처음엔 unordered_map을 두 개 써서 풀었지만, unordered_map의 노드 기반 구조의 큰 메모리 할당, 해싱과 해시 충돌 등의 오버로딩 때문에 vector를 쓰는 것보다 메모리, 시간 모두 크게 나왔다. 상황에 맞는 컨테이너를 쓰는 것이 중요한 것 같다.

또한 unordered_map을 쓰는 경우엔 혹시 모를 해시 충돌을 방지하기 위해 reserve로 넉넉한 공간 할당, max_load_factor 조절을 하는 것이 좋다!