백준 1620번 '나는야 포켓몬 마스터 이다솜' 시간초과 해결기

✨ Written with Claude

문제 상황

백준 1620번 "나는야 포켓몬 마스터 이다솜" 문제를 vector → set → unordered_map 순으로 시도했는데 계속 시간초과가 발생했다.

tmi) 문제가 정말 쓸데없이(...) 긴데, 맨 밑 문장만 읽어도 된다. 사실 입력 파트부터 봐도 무방할 듯

초기 접근법과 문제점

이 문제의 요구사항은 쿼리 값(input)이 숫자면 도감의 해당 인덱스의 값(문자열)을,
input이 문자열이면 도감의 해당 값이 몇번째인지를 출력해야 된다.
이를 줄여서 각각 인덱스 검색, 문자열 검색이라고 하겠다.

1차 시도: Vector 사용

• 결과: 시간 초과
• 원인: 인덱스 검색 시 O(1)이지만, 문자열 검색 시 O(N) 시간복잡도 소요

2차 시도: Set 사용

set<string> pokemons;
// 인덱스 검색: 인덱스에 접근 불가해서 순회 필요
// 예시 코드) 3번째 포켓몬을 찾고 싶다면 (0-based index) 
...
int target_index = 2; 

// 방법 1: iterator로 순회 
auto it = pokemons.begin(); 
advance(it, target_index); // iterator를 target_index만큼 이동
cout << "3번째 포켓몬: " << *it << '\n'; 

// 방법 2: 직접 순회 (더 직관적) 
int current_index = 0; 
for (const auto& pokemon : pokemons) { 
	if (current_index == target_index) { 
		cout << "3번째 포켓몬: " << pokemon << '\n'; 
		break; 
	} 
	current_index++; 
}
...
// 문자열 검색: find() 메소드 활용하여 O(logN)

• 결과: 시간 초과
• 원인: 인덱스 검색 시 for문을 돌려야 하므로 O(N) (+ insert 시 자동 정렬되어 순서가 다 바뀜, 문제와 부적합한 자료구조)

3차 시도: Unordered Map (단방향)

...
unordered_map<int, string> pokemons;
for (int i = 0; i < N; i++) {
    string mon;
    cin >> mon;
    pokemons[i] = mon;
}
...
// 문제가 있던 부분
for (const auto& pair : pokemons) {
    if (pair.second == target) {  // 전체 맵을 순회하며 검색
        cout << pair.first + 1 << '\n';
        break;
    }
}
...

• 결과: 시간 초과
• 원인: 문자열 검색 시 여전히 O(N) (문자열 키 값으로 직접 접근 불가)

근본 원인 분석

문제의 핵심은 양방향 검색이 아닌 한 방향으로만 해결하려 했다는 점이다.

• 인덱스 → 이름: O(1)에 접근 가능
• 이름 → 인덱스: 매번 전체 자료구조를 순회하며 찾아야 함, O(N)
• M개의 쿼리 × N번 순회 = O(M×N) 시간복잡도 💣

해결책: 양방향 매핑

핵심 아이디어

두 개의 Unordered Map을 사용하여 양방향 매핑을 구현한다.

• idxToName: 인덱스 → 이름 매핑, O(1)
• nameToIdx: 이름 → 인덱스 매핑, O(1)

제출한 코드

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    cin >> N >> M;

    unordered_map<int, string> idxToName;  // 인덱스 -> 이름
    unordered_map<string, int> nameToIdx;  // 이름 -> 인덱스

    // 입력받으면서 양방향 매핑 구축 - O(N)
    for (int i = 1; i <= N; i++) {
        string name;
        cin >> name;
        idxToName[i] = name;
        nameToIdx[name] = i;
    }

    // 쿼리 처리 - O(M)
    for (int i = 0; i < M; i++) {
        string query;
        cin >> query;
        
        if (isdigit(query[0])) {
            cout << idxToName[stoi(query)] << '\n';  // O(1)
        } else {
            cout << nameToIdx[query] << '\n';        // O(1)
        }
    }
    
    return 0;
}

성능 비교

양방향 매핑을 쓰면 약 50,000배의 성능 향상이 가능하다.

추가 최적화 요소

1. 입출력 최적화

ios_base::sync_with_stdio(false);
cin.tie(NULL);

• C와 C++ 입출력 동기화 해제
• cin과 cout 연결 해제로 버퍼링 최적화
  ⚠️ 주의) 위 구문 실행 시 scanf, printf 함수 사용 불가

2. 검색이 더 빠른 자료구조?

• unordered_map: 해시테이블 기반, 평균 O(1) 검색
• map: 이진탐색트리 기반, O(logN) 검색
• 이 문제에서는 정렬이 필요 없으므로 unordered_map이 더 적합하다.

핵심 레슨런

1. 양방향 검색의 함정

전체 성능은 가장 느린 부분에 의해 결정된다.
한 방향(인덱스→이름) 접근은 빠르게 해결되는데, 반대 방향(이름→인덱스) 접근에서 병목이 생기면? 양방향을 고려해보자.

2. 메모리 vs 시간 트레이드오프 고려하기

메모리를 2배 쓰는 대신 시간을 50,000배 절약할 수 있다면 명백하게 이득이다.
보통의 알고리즘 문제는 메모리 제한보다 시간 제한이 더 엄격한 경우가 많다고 한다.

3. unordered_map의 양면성

검색 연산이 평균적으로는 O(1)의 시간복잡도를 갖지만 최악의 경우 O(N)까지 갈 수 있다.
C++에서는 해시 충돌 방지를 위한 최적화가 잘 되어있어서 실제로는 안정적이라고 한다.
입출력 최적화와 함께 쓰면 효과가 배가 된다.

결론

이번 문제를 통해 양방향 검색도 고려해볼 수 있겠다는 유연한 사고 방식을 얻었다. 한쪽만 최적화하고 다른 쪽을 간과하면 전체 성능이 down된다.
특히 코테에서는 시간 제한이 더 빡세기 때문에 메모리를 조금 더 써서라도 시간을 확실하게 줄이는 것이 현명한 선택이다.
각 자료구조의 특성(장단점)을 잘 기억해두고 알고리즘 문제의 요구사항 시간복잡도 계산 시 적재적소에 적용해봐야겠다.