[백준 1920번] 수 찾기 (C++, Python)

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

1920번: 수 찾기

이번 포스트에서는 백준 알고리즘 문제인 수 찾기를 포스트 하겠습니다.

 

해당 문제는 solved.ac 기준 실버 4에 위치한 문제입니다.

 

먼저 문제입니다.

입력으로 N과 N개의 정수, M과 M개의 정수를 입력받습니다.

 

이때, M개의 수들이 N개의 정수 배열에 존재하는지 확인하여 출력하는 문제입니다.

 

해당 문제는 시간제한이 1초이고, N이 최악의 경우 10만 까지 주어지므로, 이중 for문을 통해서 탐색하는 경우 시간복잡도가 O(N^2)로 해결이 불가능합니다.

 

따라서, N개의 정수를 퀵정렬을 통해 정렬하고, 이진탐색으로 수를 탐색하여 O(N log N)의 시간복잡도로 해결합니다.

 

먼저 C++ 코드입니다.

 

#include <iostream>
 
using namespace std;
 
int binarySearch(int* arr, int n, int target) {
    int left = 0;
    int right = n - 1;
 
    while(left <= right) {
        int mid = (left + right) / 2;
        if(arr[mid] < target)
            left = mid + 1;
        else if(arr[mid] > target)
            right = mid - 1;
        else
            return 1;
    }
    return 0;
}
 
int compare(const void* a, const void* b) {
    return *(int*)a > *(int*)b ? 1 : (*(int*)a < *(int*)b ? -1 : 0);
}
 
int main() {
    int n;
    cin >> n;
 
    int arr[n];
    for(int i = 0; i < n; i++)
        cin >> arr[i];
 
    int m;
    cin >> m;
    
    int tar[m];
    for(int i = 0; i < m; i++)
        cin >> tar[i];
 
    qsort(arr, n, sizeof(int), compare);
 
    for(int i = 0; i < m; i++)
        cout << binarySearch(arr, n, tar[i]) << "\n";
 
    return 0;
}    

다음은 Python 코드입니다.

 

def binarySearch(arr, end, target) :
    left = 0
    right = end - 1
 
    while left <= right :
        mid = (left + right) // 2
        if arr[mid] < target :
            left = mid + 1
        elif arr[mid] > target :
            right = mid - 1
        else :
            return 1
    return 0
 
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
 
a.sort()
 
for i in range(m) :
    print(binarySearch(a, n, b[i]))

해당 문제는 시간제한과 N의 최악의 경우를 보고 O(N^2)의 시간복잡도를 가지는 방법으로 안된다는 것을 빠르게 파악하면 쉽게 떠올릴 수 있는 문제였습니다. 위 C++ 코드에서는 퀵정렬을 사용하였지만, 합병정렬로도 해결이 가능한 문제이므로, 구현해 보시는 것을 추천합니다.

다음 포스트에서도 다른 백준 알고리즘으로 포스트 하도록 하겠습니다. 감사합니다.