[2776번]암기왕

www.acmicpc.net/problem/2776

2776번: 암기왕

수첩1, 수첩2에 적힌 수를 각각 입력받아 수첩2의 번호가 수첩1에 있었는지(0, 1) 출력하는 문제였습니다.

 

처음에 해시를 사용하여 풀었다가 시간초과가 나서 이분탐색을 사용하여 풀었습니다.

이분탐색에서도 시간초과가 났었는데, cstdio를 사용하니 해결되었습니다!

 

1. 정렬
2. left = 0, right = N-1
3. mid = (left+right)/2
4. mid가 가리키는 값이면 return
5. mid가 가리키는 값보다 클 때 -> right = mid + 1
6. mid가 가리키는 값보다 작을 때 -> left = mid - 1 => 3번으로 돌아감

 

이분탐색

int left = 0, right = N-1;

while(right >= left){
  int mid = (left + right)/2;
  if(v[mid]==n){
    ans = 1;
    break;
  }
  else if(v[mid]>n){
    right = mid -1;
  }
  else{ //v[mid]<n
    left = mid + 1;
  }

 

전체코드

#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

int main(){

    int T;
    scanf("%d", &T);

    for(int i = 0; i<T; i++){
        vector<int> v;
        int N;
        scanf("%d", &N);

        for(int i = 0; i<N; i++){
            int n;
            scanf("%d", &n);
            v.push_back(n);
        }

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

        scanf("%d", &N);

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

            int left = 0, right = N-1;
            int ans = 0;
            while(right >= left){
                int mid = (left + right)/2;
                if(v[mid]==n){
                    ans = 1;
                    break;
                }
                else if(v[mid]>n){
                    right = mid -1;
                }
                else{ //v[mid]<n
                    left = mid + 1;
                }
            }
            printf("%d\n", ans);
        }
    }
}