[C/C++] 수 찾기 (백준 1920)

문제

 

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

입력

 

5
4 1 5 2 3
5
1 3 7 9 5

 

출력

 

1
1
0
0
1

 

풀이

 

이제 본격적으로 이분 탐색을 사용해서 문제를 풀게 되었습니다. 제한시간 때문에 이분 탐색을 꼭 필요로하는데 이분 탐색이란 오름차순(중요)으로 정렬된 배열에서 기존 선형 탐색보다 훨씬 바른 방법으로 수를 찾는 탐색법입니다.

 

순서는 다음과 같습니다.

 

1. 중간값을 찾는다.

2. 목표값과 중간값을 비교하여 목표값이 중간값보다 큰지 작은지 판별하고 목표값이 존재하지 않는 범위의 수는 버린다.

ex)1 2 3 5 4 에서 목표값이 5라면 중간값 3을 기준으로 1과 2를 버리고 5와 4 사이에서 탐색을 진행합니다.

3. 그렇게 나머지 배열에서 1과 2를 반복합니다.

 

위의 순서를 통해서 이분 탐색을 진행하는데 코딩 테스트를 대비하기 위해서는 위의 원리를 이용해서 풀이를 한 번 해보고 STL을 통해서 더욱 쉽게하는 법 두 가지 다 알아야하는 것 같습니다.

 

이 문제는 앞서 주어지는 배열을 먼저 오름차순으로 정렬을 진행한 후 그 다음 주어지는 각각의 수들을 가지고 이분탐색을 진행하면 쉽게 풀이가 가능합니다.

 

코드

 

 

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(void){
    int * first;
    int * second;
    int n, m;

    //첫 배열 초기화
    scanf("%d", &n);
    first = new int[n];

    for(int i = 0 ; i < n ; i++){
        int temp;
        scanf("%d", &temp);

        first[i] = temp;
    }

    sort(first, first+n);

    //두 번째 배열 초기화
    scanf("%d", &m);
    second = new int[m];

    for(int i = 0 ; i < m ; i++){
        int temp;
        scanf("%d", &temp);

        second[i] = temp;
    }

    for(int i = 0 ; i < m ; i++){
        if(binary_search(first, first+n,second[i])){
            printf("%d\n", 1);
        }
        else {
            printf("%d\n", 0);
        }
        
    }

    return 0;
}

여기서 중요한 부분은 함수도 함수지만 오름차순으로 선 정렬을 하고 코드를 진행했다는 점 입니다. 그래서 중간에 탐색을 진행해야하는 first 배열에 sort 함수를 적용하여 정렬을 먼저 진행했습니다.

 

그리고 algorithm의 binary_search를 사용했습니다.

 

binary_search(시작, 끝, 찾을 수)

 

오름차순이 되어있는 배열에서 사용해야한다는 것을 기억하고 가면 좋을 것 같습니다.