백준 1764번 '듣보잡' 시간초과 해결기

✨ Written with Claude

문제 상황

백준 1764번 "듣보잡" 문제를 vector로 해결했더니 시간초과가 발생했다.

초기 접근법과 문제점

// 문제가 있던 코드
for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
        if (unseens[i] == unheards[j]) {  // 이중 반복문으로 비교
            cnt++;
            result.push_back(unseens[i]);
        }
    }
}

시간복잡도: O(N × M)

• unseens 벡터, unheard 벡터의 각 원소들을 모두 순차 탐색함
• N과 M이 클수록 기하급수적으로 시간이 늘어남

근본 원인 분석

문제의 핵심은 탐색 방식에 있었다.

• 순차 탐색: 벡터에서 특정 원소를 찾으려면 처음부터 끝까지 하나씩 확인 → O(N)
• 이중 반복문: 두 벡터 간의 모든 조합을 확인하는 brute force 방식 → O(N×M)

해결책: Set 자료구조 활용

Set의 장점

• 이진 탐색 트리 기반으로 구현되어있음
• find() 메소드: O(logN) 시간에 원소 검색 가능
• 내부적으로 정렬된 상태 유지

제출한 코드

#include <set>

set<string> unheardSet;
// N개의 입력을 set에 저장 - O(NlogN)
for (int i = 0; i < N; i++) {
    cin >> unheard;
    unheardSet.insert(unheard);
}

vector<string> result;
// M개의 입력에 대해 set에서 검색 - O(MlogN)
for (int i = 0; i < M; i++) {
    cin >> unseen;
    if (unheardSet.find(unseen) != unheardSet.end()) {
        result.push_back(unseen);
    }
}

개선된 시간복잡도: O(NlogN + MlogN) ~= O(NlogN)

성능 비교

벡터를 안 쓰고 집합을 쓰면 약 13,000배의 성능 향상이 이뤄진다.

추가로 최적화 가능한 경우

1. unordered_set (해시테이블)

#include <unordered_set>
...
unordered_set<string> unheardSet;

for (int i = 0; i < N; i++) {
    cin >> unheard;
    unheardSet.insert(unheard);
}

for (int i = 0; i < M; i++) {
    cin >> unseen;
    if (unheardSet.find(unseen) != unheardSet.end()) {
        result.push_back(unseen);
    }
}
...

• 평균 시간복잡도: 검색 시 O(1)
• 최악의 경우: 해시 충돌 시 O(N)
• 메모리 사용량: set 자료구조보다 높음 - 이유
  해시테이블을 구현하기 위해 버킷 배열을 미리 할당하고, 해시 충돌 처리를 위한 추가 공간도 필요하기 때문에 set(이진 탐색 트리)보다 메모리를 더 많이 사용한다고 한다.

2. set 두 개 생성 후 교집합 찾기

...
set<string> result;
set_intersection(unheardSet.begin(), unheardSet.end(),
                 unseenSet.begin(), unseenSet.end(),
                 inserter(result, result.begin()));
...

핵심 레슨런

1. 자료구조 선택의 중요성

• Vector: 순차 접근에 최적화, 검색은 비효율적임
• Set: 검색과 정렬에 최적화, 메모리는 더 사용함
• 목적에 맞는 자료구조 선택이 알고리즘의 성능을 좌우한다!

2. 시간복잡도 분석 습관 들이기

• 코드 작성 전 예상 시간복잡도 계산하기
• N, M의 범위를 확인하고 제한시간 내 처리 가능한지 판단하기
• 범위가 클 때는 O(N²) 이상의 알고리즘 지양하기

3. 최적화 우선순위

1. 알고리즘 설계
2. 자료구조 선택
3. 구현 최적화

4. 문제 해결 프로세스

문제 분석 → 시간복잡도 예측 → 자료구조 선택 → 구현 → 테스트

결론

단순히 "시간초과가 났으니 다른 자료구조를 써야겠네"가 아니라, 기존의 방식은 왜 느린지 분석하고 새로운 방식은 어떤 특성 때문에 필요한 것인지 파악한 후 적절한 도구를 선택해야겠다.

이번 경험을 통해 탐색이 빈번한 상황에서는 set/map 계열 자료구조를 우선 고려해볼 수도 있겠다는 교훈을 얻었다.