[BOJ] 1920 수 찾기

간단히 풀려면 정말 간단하다. 그냥 입력받은 수 배열에 넣고 그 이후 숫자 입력 받을때마다 반복문으로 체크해보면 된다.

#include <stdio.h>
#define MAX_SIZE 100000

int main() {
    int n, m;
    int t, temp;
    int arr[MAX_SIZE];

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

    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        t = 0;
        scanf("%d", &temp);
        for(int j = 0; j < n; j++) {
            if(arr[j] == temp) {
                printf("1\n");
                t = 1;
                break;
            }
        }
        if(t == 0) printf("0\n");
    }

    return 0;
}

그리고 이렇게 대충 반복문으로 코드를 짜면 정말 당연하게도

빨간색 시간초과를 볼 수 있다.

 

그렇다면 이 문제는 탐색알고리즘을 써야 된다는 건데 그 중 제일 간단하다고 생각하는 이진탐색을 사용했다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100000

int compare(const void *a, const void *b);
int bst(int* arr, int start, int end, int target);

int main() {
    int n, m;
    int t, temp;
    int arr[MAX_SIZE];

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

    qsort(arr, n, sizeof(int), compare);
    
    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        scanf("%d", &temp);
        if(bst(arr, 0, n, temp) != -1) printf("1\n");
        else printf("0\n");
    }

    return 0;
}

int compare(const void *a, const void *b) {
    if(*(int *)a > *(int *)b) return 1;
    if(*(int *)a < *(int *)b) return -1;
    if(*(int *)a == *(int *)b) return 0;
}

int bst(int* arr, int start, int end, int target) {
    if(start > end) return -1;
    int mid = (start + end) / 2;
    if(arr[mid] > target) return bst(arr, start, mid - 1, target);
    else if(arr[mid] < target) return bst(arr, mid + 1, end, target);
    else return mid;
}

 이렇게 예쁜 이진탐색코드를 작성했더니 틀렸다고 나온다. 이때부터 맞왜틀을 계속 외치기 시작한다. 분명 예제도 정상적으로 작동하고 다른거 이상한거 넣어도 정상적으로 작동하는데 왜 안되지?

 

그때부터 눈이 돌아가서 하나씩 바꿔보기 시작하다가 어쩌다 반례를 찾았다.

원래라면 결과값이 0이 나와야 하지만 1이 나와버렸다. 반례를 찾았으니 이것을 해결하기 위해 열심히 디버거를 돌려봤는데, 

 

배열에서 우리가 입력을 하고 사용하는 크기는 1이다. 즉, 인덱스는 0까지만 사용한다. 그러나 두번째 bst함수를 들어갔을 때 start와 end가 1이 되고 이에 따라 mid값도 1이 된다. 여기서 arr[1]을 불러왔을 때 이 값이 0이 나오고 그게 target과 같은 수라서 최종 결과로 1이 출력되는 것이다.

 

 이 결과가 결국엔 사용가능한 index를 넘어가서 이러한 결과가 나온다고 생각해서 bst함수에 함수의 크기 len이라는 인자를 추가해주고 처음 탈출 조건에 start > len이라는 조건을 추가해줬다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100000

int compare(const void *a, const void *b);
int bst(int* arr, int start, int end, int target, int len);

int main() {
    int n, m;
    int t, temp;
    int* arr;

    scanf("%d", &n);
    arr = malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    qsort(arr, n, sizeof(int), compare);

    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        scanf("%d", &temp);
        if(bst(arr, 0, n, temp, n) != -1) printf("1\n");
        else printf("0\n");
    }

    return 0;
}

int compare(const void *a, const void *b) {
    if(*(int *)a > *(int *)b) return 1;
    else if(*(int *)a < *(int *)b) return -1;
    else return 0;
}

int bst(int* arr, int start, int end, int target, int len) {
    if(start > end || start >= len) return -1;
    int mid = (start + end) / 2;
    if(arr[mid] > target) return bst(arr, start, mid - 1, target, len);
    else if(arr[mid] < target) return bst(arr, mid + 1, end, target, len);
    else return mid;
}

 중간에 배열이 포인터 동적할당으로 바꼈는데 혹시나 배열 크기문제 때문인가 싶어서 수정했었는데 아니였다. 그래도 그냥 메모리 크기 생각해서 놔뒀다.