백준 1920 수 찾기

문제링크 : https://www.acmicpc.net/problem/1920

아이디어

• 일단 브루트포스로 모두 순회하면서 탐색할 경우
  • 쿼리 M개동안 N번을 돌아야함
  • 시간복잡도 : O(NM) = 1e10 > 시간초과
• 이진탐색 사용해서, 해당 값 찾기
  • 찾은다음 인덱스 반환해서 같은 값인지확인

시간복잡도 계산

• N개 정렬 : O(NlgN)
• 쿼리 M번 : O(M)
• 이진탐색 : O(lgN)
• 총합 : O(NlgN + MlgN) = O(MlgN)

자료구조

• 정수 저장 : map[100010];
  • 모든 정수 범위 : 2^31보다 작음 > INT 가능

코드(C++)

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int map[100010];
 
int binsearch(int st, int en, int tar) {
    if(st==en) {
        // 타겟이랑 값이 같은지 확인
        if(map[st] == tar) return 1;
        return 0;
    }
    
    // 이진탐색 lower bound
    int mid = (st+en)/2;
    if(map[mid] < tar) return binsearch(mid+1, en, tar);
    else return binsearch(st, mid, tar);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    for(int i=0; i<N; i++) cin >> map[i];
    sort(map, map+N);
    
    int M; cin >> M;
    for(int i=0; i<M; i++) {
        int num; cin >> num;
        cout << binsearch(0,N-1,num) << '\n';
    }
    return 0;
}

문제유형

• 이진탐색 - 모든케이스에서 이분탐색

비슷한 문제

• https://www.acmicpc.net/problem/1920
• https://www.acmicpc.net/problem/1300
• https://www.acmicpc.net/problem/1939
• https://www.acmicpc.net/problem/8983
• https://www.acmicpc.net/problem/3020
• https://programmers.co.kr/learn/courses/30/lessons/43238
• https://www.acmicpc.net/problem/2143