[백준] 10815번: 숫자 카드

10815번: 숫자 카드

 

 

이 문제는 이분 탐색 문제에 속합니다.

간단한 이분 탐색의 경우 STL에 속한 binary_search로 해결이 되지만 조금 복잡해질 경우 실제로 구현해야 합니다.

 

이 문제는 간단한 이분 탐색의 문제이기 때문에 STL을 사용해도 되지만 저는 일반적인 이분 탐색 방법을 구현해서 코드를 작성해보았습니다.

 

일반적인 이분 탐색의 방법은 굉장히 간단합니다.

 

이분 탐색은 정렬된 객체들을 이용해야지만 탐색할 수 있는 방법 중 하나인데요.

먼저 left, right 인덱스를 잡고,

left 가 right보다 커지면 종료되는 while 문 안에서 mid를 left와 right를 활용해서 잡아줍니다.

 

이 mid 값이 원하는 값일 때, 종료하면 됩니다.

원하는 값이 아니라면 크기를 비교하여 mid 왼쪽 구간, mid 오른쪽 구간 중 원하는 구간을 선택합니다.

이 선택 방법은 left와 right 값을 mid를 활용해서 바꾸어주는 방법으로 충분합니다.

 

 

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

int N, M;
vector<int> card;
vector<int> num;

void input() {
  cin >> N;
  card.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> card[i];
  }
  sort(card.begin(), card.end());

  cin >> M;
  num.resize(M);
  for (int i = 0; i < M; i++) {
    cin >> num[i];
  }
}

int checkCard(int num) {
  int left = 0;
  int right = N - 1;

  while (left <= right) {
    int mid = (left + right) / 2;

    if (num == card[mid]) {
      return 1;
    }
    else if (num < card[mid]) {
      right = mid - 1;
    }
    else {
      left = mid + 1;
    }
  }
  
  return 0;
}

void printAnswer() {
  for (int i = 0; i < M; i++) {
    cout << checkCard(num[i]) << ' ';
  }
}

int main() {

  ios::sync_with_stdio(false);
  input();
  printAnswer();

  return 0;
}