알고리즘 문제풀이/C++

[C++] 백준 문제 풀이: 시간 초과(TLE) 해결! Vector vs Set의 결정적 차이

aerimi-code 2026. 2. 8. 21:03

1. 문제 정보

  • 문제 번호: 1181번
  • 문제 이름: 단어 정렬
  • 문제 요약:
    1. 길이가 짧은 것부터
    2. 길이가 같으면 사전 순으로
    3. 단, 중복된 단어는 하나만 남기고 제거해야 한다.
  • 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래 조건에 따라 정렬하는 프로그램을 작성하시오.

 

2. 첫 번째 시도: Vector + Find (시간 초과 ❌)

처음에는 가장 익숙한 vector를 사용했다. 입력받을 때마다 find 함수로 중복을 검사하고, 마지막에 sort를 하는 방식이다.

 

💻 코드

#include <iostream>
#include <vector>
#include <algorithm> // find, sort 사용
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> numbers;
    
    // 1. 입력받으며 중복 제거
    for (int i = 0; i < n; i++){
        int num;
        cin >> num;
        
        // 벡터 전체를 뒤져서 없으면 넣는다 (여기서 문제 발생!)
        if(find(numbers.begin(), numbers.end(), num) == numbers.end()){
            numbers.push_back(num);
        }
    }

    // 2. 정렬
    sort(numbers.begin(), numbers.end());

    // 3. 출력
    for(const int &n : numbers){
        cout << n << endl;
    }

    return 0;
}

 

🧐 왜 시간 초과가 났을까? (원인 분석)

컴파일러에서는 잘 돌아가지만, 입력값($N$)이 커지면 치명적인 성능 문제가 발생한다. 원인은 바로 find 함수다.

  1. find의 시간 복잡도: 벡터의 처음부터 끝까지 다 뒤져야 하므로 O(N)이다.
  2. 반복문 내부의 find: N개의 입력을 받으면서 매번 find(O(N))를 실행한다.
  3. 전체 시간 복잡도: O(N ) X O(N) = O(N^2)

만약 N이 100,000이라면, 연산 횟수는 대략 100억 번이 된다. 보통 1초에 1억 번 연산이 가능한데, 이건 당연히 시간 초과다.

3. 두 번째 시도: Set 활용 (정답 ✅)

이 문제를 해결하기 위해 std::set 자료구조를 사용했다. set은 중복 허용 안 함 + 자동 정렬이라는 강력한 특징을 가지고 있다.

 

💻 코드

#include <iostream>
#include <set>
using namespace std;

int main() {
    int n;
    cin >> n;

    set<int> numbers; // 자동으로 중복 제거 + 정렬됨

    // 1. 입력 (그냥 넣기만 하면 됨)
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        numbers.insert(num); // 중복이면 알아서 무시, 들어갈 때 정렬됨
    }

    // 2. 출력
    for (int num : numbers) {
        cout << num << "\n";
    }

    return 0;
}

 

🚀 성능 개선 분석

  • 삽입(insert)의 시간 복잡도: set은 내부적으로 균형 이진 탐색 트리(Balanced BST) 구조라 삽입에 $O(log N)이 걸린다.
  • 전체 시간 복잡도: $N$개를 넣으니까 O(Nlog N).

4. 깊이 알기: Set은 어떻게 동작하는가? 🌳

C++의 set은 단순한 "주머니"가 아니다. 내부적으로 레드-블랙 트리(Red-Black Tree)라는 자료구조로 구현되어 있다.

  1. 자동 정렬: 트리의 특성상 데이터를 넣는 순간(Insert), 크기를 비교해서 왼쪽/오른쪽 자리를 찾아 들어간다. 그래서 항상 정렬된 상태를 유지한다.
  2. 중복 제거: 데이터를 넣을 때 이미 트리에 같은 값이 있으면, 아예 넣지 않고 무시한다.
  3. 순회: for (int num : numbers) 처럼 순회하면 트리 구조를 따라 작은 값부터(오름차순) 차례대로 나온다.

5. 꿀팁: 내림차순 정렬하기 (greater<int>)

set은 기본적으로 오름차순(less<int>)이다. 만약 큰 숫자부터 나오게 하고 싶다면 어떻게 할까?

선언할 때 비교 기준(Comparator)만 바꿔주면 된다.

// 오름차순 (기본)
set<int> s1 = {5, 3, 8, 3, 1}; 
// 출력: 1 3 5 8

// 내림차순 (greater 사용)
set<int, greater<int>> s2 = {5, 3, 8, 3, 1};
// 출력: 8 5 3 1

📝 배운 점 요약 (TIL)

  1. 시간 복잡도의 중요성: vector에서 find를 반복문 안에 넣으면 O(N^2)가 되어 위험하다.
  2. Set의 강력함: set은 단순 집합이 아니라 이진 탐색 트리다.
    • 중복 제거 자동
    • 입력 시 자동 정렬 (O(log N))
  3. 유연한 활용: 오름차순이 기본이지만, set<int, greater<int>>를 쓰면 내림차순 자동 정렬도 가능하다.

앞으로 "중복 제거"와 "정렬" 키워드가 같이 보이면 고민하지 말고 set을 꺼내야겠다!