[백준/C++] 1920번: 수 찾기 - 시간 초과를 피하는 자료구조와 입출력 최적화

1. 문제 정보

• 문제 번호: 1920번
• 문제 이름: 수 찾기
• 문제 링크: https://www.acmicpc.net/problem/1920
• 문제 요약:
• N개의 정수가 주어졌을 때, 이후에 주어지는 M개의 정수들이 기존 N개의 정수 안에 존재하는지 확인하는 프로그램을 작성하시오. (존재하면 1, 없으면 0 출력)

 

2. 접근 방법 (알고리즘)

❌ 첫 번째 시도: Vector + std::find (시간 초과)

가장 단순하게 vector에 값을 저장하고 find 함수로 하나씩 찾는 방식을 선택했다.

• 문제점: std::find는 벡터의 처음부터 끝까지 확인하는 선형 탐색이다.
• 시간 복잡도: 입력 N, 쿼리 M일 때 O(N X M).
• 결과: N, M이 최대 10만일 경우 연산 횟수가 100억 번에 달해 시간 초과가 발생.

❌ 두 번째 시도: std::set 사용 (여전히 시간 초과?)

탐색 속도를 높이기 위해 내부적으로 이진 탐색 트리(Red-Black Tree) 구조를 가지는 set을 사용.

• 성능: 탐색 속도가 O(log N)으로 빨라짐. 전체 복잡도는 O(M log N).
• 결과: 하지만 여전히 백준에서는 시간 초과가 발생했습니다. 로직의 문제가 아니라 입출력 속도가 문제!

✅ 최종 접근: set + 입출력 최적화 (성공)

C++의 기본 cin/cout은 매우 느리다. 

최적화 하는 코드가 필요!

3. 코드 구현 (정답)

#include <iostream>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    // [최적화 1] C의 stdio와 C++의 iostream 동기화 해제
    ios::sync_with_stdio(false);
    // [최적화 2] cin과 cout의 묶음을 해제 (불필요한 flush 방지)
    cin.tie(nullptr);

    int n, m;
    set<int> numbers;
    
    // N개의 숫자 입력 및 삽입
    cin >> n;
    for(int i = 0; i < n; i++) {
        int num;
        cin >> num;
        numbers.insert(num);
    }
    
    // M개의 숫자 탐색
    cin >> m;
    for(int i = 0; i < m; i++) {
        int num;
        cin >> num;
        // set의 find 함수는 O(log N)의 속도를 보장함
        if(numbers.find(num) != numbers.end()) {
            cout << "1\n";
        } else {
            cout << "0\n";
        }
    }

    return 0;
}

---

4. 배운 점 & 회고 (TIL) ✍️

① 탐색 알고리즘의 시간 복잡도

• vector + find: 순차적으로 다 뒤져야 한다. O(N) 
• set (Red-Black Tree): 데이터를 넣을 때부터 정렬하며 들어가기 때문에 반씩 나눠서 찾는 이진 탐색 기법을 써서 빠르다.

② C++ 입출력 최적화 비법

로직이 완벽해도 입출력 양이 많으면(보통 10만 건 이상) 아래 두 줄이 필수.

1) ios::sync_with_stdio(false);

• 의미: C++의 iostream과 C의 stdio 사이의 동기화를 끊습니다.
• 효과: 입출력 속도가 비약적으로 향상됩니다.
• 주의: 이제 scanf/printf와 cin/cout을 섞어 쓰면 출력 순서가 꼬일 수 있으므로 하나만 써야 합니다.

2) cin.tie(nullptr);

• 의미: cin과 cout의 결합을 해제합니다.
• 효과: 원래는 입력받기 전에 cout의 버퍼를 비우는(flush) 작업이 자동으로 일어나는데, 이를 막아 시간을 절약합니다. endl 대신 \n을 쓰는 것도 같은 이유입니다.

💡 추가 팁

사실 이 문제에서 더 빠른 성능을 원한다면 set보다 unordered_set을 사용하는 것이 좋다. set은 정렬을 유지하지만, unordered_set은 해시 테이블을 사용하여 탐색 시간이 평균 $O(1)이기 때문입니다.

이번 기회를 통해 알고리즘 문제 해결에는 로직만큼이나 데이터 양에 따른 입출력 환경 최적화가 얼마나 중요한지 깊이 깨달았습니다!