[백준/C/Python] 1920 - 수 찾기

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

---

구현 과정

c로 코드를 짤 때 처음에는 이중 for문을 이용해 입력받은 수, 찾으려는 수 배열을 모두 순회하는 방법을 택했다. 그랬더니 시간 초과가 나서 더 효율적인 방법이 뭐가 있을지 찾아봤다.

C에서의 구현

이분 탐색

이분 탐색을 위해서는 배열이 미리 정렬되어 있어야 한다. 이를 위해 compare() 함수를 만들고, main 내에서 qsort() 를 사용한다.

int compare(const void *a, const void *b) {
    int num1 = *(int *)a;
    int num2 = *(int *)b;

    if (num1 < num2)
        return -1;
    else if (num1 > num2)
        return 1;
    else
        return 0;
}

qsort(nums, n, sizeof(n), compare);

이분 탐색 함수는 아래와 같이 만든다.

int binSearch(int *array, int size, int target) {
    int low = 0;
    int high = size - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (array[mid] == target)
            return 1;
        else if (array[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return 0;
}

찾을 숫자의 개수 m을 입력받은 후 while (m--) 동안 수를 입력받고, 이분탐색 수행하는 과정을 반복한다.

while (m--) {
    int findNum;
    scanf("%d", &findNum);
    printf("%d\n", binSearch(nums, n, findNum));
}

Python에서의 구현

입력받는 데이터의 수가 매우 많을 수도 있기 때문에 파이썬에서도 그냥 n = int(input()) 하는 대신, sys.stdin.read 를 사용한다.

이분 탐색

배열 정렬은 sort() 를 이용한다. 이분 탐색 함수는 c에서의 함수와 똑같다.

def binSearch(array, target):
    low = 0
    high = len(array) - 1;
    while (low <= high):
        mid = (low + high) // 2
        if (array[mid] == target):
            return 1
        elif (array[mid] < target):
            low = mid + 1
        else:
            high = mid - 1
    return 0

main() 이용

코드 실행 시 __name__ 변수를 __main__ 으로 설정하게 된다

if __name__ == "__main__":
    main()

main() 내에서의 과정

입력을 한꺼번에 받은 뒤, split()을 이용해 공백을 기준으로 나누어 변수, 리스트에 저장한다.

data = input().split()
    n = int(data[0])
    nums = list(map(int, data[1:n+1]))
    nums.sort()

    m = int(data[n+1])
    queries = map(int, data[n+2:])

---

전체 코드

C

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    int num1 = *(int *)a;
    int num2 = *(int *)b;

    if (num1 < num2)
        return -1;
    else if (num1 > num2)
        return 1;
    else
        return 0;
}

int binSearch(int *array, int size, int target) {
    int low = 0;
    int high = size - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (array[mid] == target)
            return 1;
        else if (array[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return 0;
}

int main() {
    int n;
    scanf("%d", &n);

    int *nums = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    qsort(nums, n, sizeof(int), compare);

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

    while (m--) {
        int findNum;
        scanf("%d", &findNum);
        printf("%d\n", binSearch(nums, n, findNum));
    }
    free(nums);
    return 0;
}

Python

import sys
input = sys.stdin.read

def binSearch(array, target):
    low = 0
    high = len(array) - 1;
    while (low <= high):
        mid = (low + high) // 2
        if (array[mid] == target):
            return 1
        elif (array[mid] < target):
            low = mid + 1
        else:
            high = mid - 1
    return 0

def main():
    data = input().split()
    n = int(data[0])
    nums = list(map(int, data[1:n+1]))
    nums.sort()

    m = int(data[n+1])
    queries = map(int, data[n+2:])

    result = [binSearch(nums, query) for query in queries]
    for res in result:
        print(res)

if __name__ == "__main__":
    main()