[백준 1920] 수 찾기 (이진탐색)

• 안녕하세요. BlockDMask 입니다. 

• 오늘은 '수 찾기' 라는 문제를 풀어보았습니다.

• 음..은근히 생각을 하게 하는 문제였습니다.
  '시간초과' 때문에;; ㅎㅎ
  170906 문제 빼먹음 -> 171008 완료

0. 제목

• 백준 1920 수 찾기 (이진탐색)

• BOJ 1920 수 찾기 (Binary Search)

1. 문제설명

N개의 정수 A[1], A[2], A[3], A[4], ..., A[N-2], A[N-1], A[N] 이 주어져 있을 때, 

이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 구현하면 됩니다.

입력 --

첫째 줄에 자연수 N(1<= N <=100,000) 이 주어집니다.

둘째 줄에는 N개의 정수 A[1], A[2], A[3], A[4], ..., A[N-2], A[N-1], A[N] 이 주어집니다.

셋째 줄에는 M (1<= M <= 100,000) 이 주어집니다.

마지막 줄에는 M 개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 됩니다.

출력 --

M개의 줄에 답을 출력하면 됩니다.

존재하면 1 출력.

존재하지 않으면 0 출력.

2. 풀이과정

Linear Search(선형탐색)을 이용하여 문제를 풀었는데 '시간초과'가 나왔습니다.

좀더 좋은 방법이 없을까 고민 끝에, 

받은 배열을 Quick Sort로 정렬을 한 후

Binary Search(이진탐색)을 이용하여 문제를 풀었습니다.

이진탐색을 구현하는 방법이 세가지 있습니다

a) 직접 구현 - 반복문을 이용한 이진 탐색

b) 직접 구현 - 재귀를 이용한 이진 탐색

c) STL 이용 - binary_search 함수 이용한 이진탐색

세가지 방법의 이진탐색의 코드는

[바로가기]에 정리해 두었습니다. (준비중..)

3. 코드

//https://www.acmicpc.net/problem/1920
//BOJ_1920_수찾기
 
#include<iostream>
#include<cstdio>
#include<algorithm>
 
using namespace std;
 
int arr[100001];
 
//이진탐색(Binary Search)을 이용하여 탐색
void Solution(int n, int key){
 
    int start = 0;
    int end = n-1;
    int mid;
 
    while(end - start >= 0){
        mid = (start + end)/2;
 
        if(arr[mid] == key){   //key 값이 배열의 중앙 값과 같을때
            printf("1\n");
            return ;
 
        }else if(arr[mid] > key) { //key 값이 배열의 중앙 값보다 작을때 (왼쪽으로)
            end = mid - 1;
 
        }else{  //key 값이 배열의 중앙 값보다 클때 (오른쪽으로)
            start = mid + 1;
        }
    }
 
    printf("0\n");
    return ;
}
 
int main(void){
 
    int n, m, tmp;
 
    //입력
    scanf("%d", &n);
 
    for(int i=0; i<n; i++){
        scanf("%d", &arr[i]);
    }
    sort(arr, arr+n);   //quick sort를 이용해 배열 오름차순으로 정렬
 
    //입력
    scanf("%d", &m);
 
    for(int i=0; i<m; i++){
        scanf("%d", &tmp);
        Solution(n, tmp);
    }
 
    return 0;
}

4. 인증

문제 출처 - https://www.acmicpc.net/problem/1920

감사합니다.트 꾹 부탁드립니다.