Algorithm/BOJ

[C++] 백준 2776번 암기왕 - 이분탐색 ( sort + binary search) / 해시맵 (unordered_map)

Rubi ❤️ 2025. 5. 11. 16:19
728x90
반응형

[C++] 백준 2776번 암기왕 - 이진 탐색 / 해시맵

🔍 문제 요약

  • 문제 링크: 백준 2776번
  • 주요 태그: 이진 탐색, 정렬, 해시맵, 자료구조

문제 설명:
연종이는 자신이 하루 동안 본 정수들을 모두 기억할 수 있다고 주장한다.
동규는 그가 진짜 암기왕인지 확인하기 위해,
연종이가 본 수(N개)와 그에게 물어본 수(M개)를 비교해
물어본 수가 수첩1에 있는지 여부를 판단하는 프로그램을 작성해보자.

💡 문제 분석

  • 입력 수의 개수는 최대 1,000,000개
  • 각 테스트 케이스마다 빠르게 검색이 가능해야 함
  • 선형 탐색(O(NM))으로는 시간 초과 발생
  • 따라서 이진 탐색 (O(log N)) 또는 해시셋 (O(1)) 방식 필요

🔑 아이디어

✔ 방법 1: 이진 탐색

  • 수첩1(N개)을 정렬한 뒤
  • 수첩2(M개)의 각 숫자에 대해 이진 탐색 수행 → 빠르게 존재 여부 판별

이진탐색의 전제조건은 정렬된 배열 또는 리스트라는 것을 기억하자!

✔ 방법 2: 해시맵

  • 수첩1을 unordered_map/set에 저장
  • 수첩2에서 key 존재 여부만 확인

→ 해시맵 풀이는 매우 간단하니 여기서는 이진 탐색 방식으로 풀어보겠습니다! 

🧩 풀이 전략

  1. 테스트 케이스 수 T 입력
  2. 각 테스트 케이스마다:
    • 수첩1 입력받고 정렬
    • 수첩2 숫자 하나씩 이진 탐색
    • 결과 출력 (있으면 1, 없으면 0)

📦 예제 입력 & 출력

  • 입력
1
5
4 1 5 2 3
5
1 3 7 9 5
  • 출력
1
1
0
0
1

🖥️ 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return true;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

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

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;
        vector<int> note1(n);
        for (int i = 0; i < n; i++) cin >> note1[i];

        sort(note1.begin(), note1.end());

        int m;
        cin >> m;
        for (int i = 0; i < m; i++) {
            int query;
            cin >> query;
            cout << (binarySearch(note1, query) ? 1 : 0) << '\n';
        }
    }

    return 0;
}

✅ 검증 및 테스트

입력값 결과
1 3 7 9 5 1 1 0 0 1

 

⏱️ 시간복잡도

  • 정렬: O(N log N)
  • 각 쿼리: O(log N)
  • 총 시간복잡도: O(T × (N log N + M log N))

✨ 결론

  • 이 문제는 "기 문제의 전형적인 예로, 정렬 + 이진 탐색 또는 해시맵을 활용하여 풀 수 있다. 
  • 실무에서도 대량의 데이터 중 존재 여부 확인은 매우 자주 등장하기때문에 익혀두자!
  • unordered_set을 사용하면 코드가 더 간단해질 수 있지만, 이진 탐색도 충분히 효율적이다.
728x90
반응형