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

https://www.acmicpc.net/problem/1920

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	293625	93304	61533	30.445%

문제

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을 출력한다.

예제 입력 1

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

예제 출력 1

1
1
0
0
1

풀이

배열에 저장된 정수 중에 값이 있는지 일일이 비교해 주기위해선 시간복잡도가 매우 커지게 됩니다. (일일이 비교했을 경우 최악의 경우 최대 n = 100000, m = 100000 이어서 10^10 만큼의 시간이 걸림)

이분 탐색 메소드를 이용해 문제를 해결하고 직접 구현까지 해보았습니다.

코드

내장 함수 사용

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  vector<int> vec;  
  int n, m, num;
  cin >> n;

  for(int i = 0; i < n; i++){
    cin >> num;
    vec.push_back(num);
  }

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

  cin >> m;
  for(int i = 0; i < m; i++){
    cin >> num;

    bool find = binary_search(vec.begin(), vec.end(), num);
    cout << find << "\n";
  }
  return 0;
}

직접 구현

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  vector<int> vec;  
  int n, m, num, find_num;
  cin >> n;

  for(int i = 0; i < n; i++){
    cin >> num;
    vec.push_back(num);
  }

  sort(vec.begin(), vec.end());
  cin >> m;

  for(int i = 0; i < m; i++){
    cin >> find_num;
    
    int start = 0, end = vec.size() - 1;
    bool found = false;
    
    while(start <= end){
      int mid = (start + end) / 2;
      
      if(vec[mid] == find_num){
        found = true;
        break;
      }

      else if(vec[mid] < find_num){
        start = mid + 1;
      }
      else
        end = mid - 1;
    }
    
    if(found)
      cout << "1" << "\n";
    else 
      cout << "0" << "\n";
  }
  
  return 0;
}

리뷰

이분 탐색(binary search)에 대해 공부 겸 문제를 풀어보았습니다. 이분 탐색은 오름차순으로 정렬된 리스트에서 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘입니다.

검색 범위를 줄이는 방법은 정렬이 되어있는 리스트에서 중간 인덱스를 기준으로 찾고자하는 값과 크기를 비교해 작으면 왼쪽을, 크면 오른쪽을 탐색하는 것입니다. 이 방법을 이용하면 비교해야하는 값을 절반 이상 줄일 수 있습니다.

c++의 algorithm 헤더에는 쉽게 이분 탐색을 해주는 binary_search 함수가 있지만 직접 구현을 해봄으로써 이분 탐색을 더 이해할 수 있었습니다.

성능