[C언어/C++] 1920번 수 찾기 + 반례 모음

안녕하세요 황지원입니다.

 

한 달 전에 정렬하는 법 몰라서 못 풀었던 문제 오늘 풀었습니다.

실버 4의 문제인데요, 푸는 방법은 이렇습니다.

n개의 정수 A[N]을 정렬해준 다음에

m개의 정수가 A안에 있는지 찾아주기만 하면 되는 간단한 문제입니다.

 

실버 4인데 이분탐색 안 쓸 줄 알고 알고리즘 고민하다가 설마 이분탐색 쓰나 봤더니 정말 이분탐색 쓰던군요.

유의하셔야 할 점은 딱히 없습니다.

정수의 범위가 -2^31 ~ 2^31 이라는 점에 유의해서 int 형이 아닌 long long을 써보세요.

 

반례 드리겠습니다.

4                      
2147483647 10 -2147483640 0 
5
0 0 0 2147483647 9 

정답

1
1
1
1
0

5
0 0 0 0 0
5 
1 1 1 1 0

정답

0
0
0
0
1

1
1
1
1

정답

1

#include <stdio.h>
void quickSort(long long arr[], int L, int R) {
      int left = L, right = R;
      int pivot = arr[(L + R) / 2];
      int temp;
      do
      {
        while (arr[left] < pivot)
            left++;
        while (arr[right] > pivot)
            right--;
        if (left<= right)
        {
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
      } while (left<= right);
    if (L < right)
        quickSort(arr, L, right);
 
    if (left < R)
        quickSort(arr, left, R);
}
int main() {
    long long arr[100000] ={}, brr[100000] = {};
    long long n, m, a;

    scanf("%lld", &n);
    for(int i = 0; i < n; i++) {
        scanf("%lld", &arr[i]);
    }

    scanf("%lld", &m);
    for(int i = 0; i < m; i++) {
        scanf("%lld", &brr[i]);
    }
    quickSort(arr, 0, n - 1);
    for(int i = 0; i < m; i++) { //이분탐색 구간입니다.
        long long end = n-1, first = 0;
        for(int j = 0; j < 20; j++) {
            if(arr[(end + first)/ 2] > brr[i]) {
                end = (end + first) / 2;
            }
            else first = (end + first) / 2;
        }
        if(arr[first] == brr[i] || arr[end] == brr[i]) {
        printf("1\n"); //줄바꿈에 유의하세요
        }
        else printf("0\n"); //줄바꿈에 유의하세요
    }
}