[C++] 백준 1920 수 찾기

www.acmicpc.net/problem/1920

1920번: 수 찾기

 

1. 서론

 

간단해 보이지만 메모리에 대해서 생각해야 하는 문제

 

2. 문제 풀이

 

두 개의 배열이 주어진다. 첫 번째 배열은 정수 배열, 두 번째 배열 역시 정수 배열인데 이 배열의 값들이 첫 번째 배열에 있는지 없는지 판단하는 것이 문제이다. 배열의 값이 존재하면 1을 아니면 0을 return 한다.

 

배열의 길이가 최대 100000까지이기 때문에 그냥 한 바퀴를 돌아서 찾으면 무조건 시간 초과가 난다.

이런 탐색 문제에서 가장 효율이 좋은 것은 정렬이 된 상태에서 하는 이진 탐색이다. 시간 복잡도는 O(logn)이다.

그래서 나는 binary_search 함수를 이용해서 풀었다. 

 

-새롭게 알게 된 점

 

그런데 이렇게 푸는 방법도 있다. 바로 set을 이용해서 배열을 만드는 것이다.

set은 노드 기반의 컨테이너이며 균형 이진트리로 구현되어 있다고 한다.

그리고 insert로 값이 들어오면 원소가 자동으로 정렬된다고 한다.

set에는 count라는 함수가 있는데 count 함수 안에 원소의 값을 넣으면 그 원소의 개수를 반환한다.

그런데 set은 원소 값의 중복이 허용되지 않기 때문에 무조건 0과 1을 반환한다.

따라서 set을 쓰면 위의 정렬된 이진 탐색과 같은 원리로 동작하게 된다. (정렬 + 이진 탐색을 한 번에 해결)

 

3. 코드 설명

 

#include <stdio.h>
#include <algorithm>

using namespace std;

int main()
{
    int n, m, i, x;
    int a[100000];

    scanf("%d", &n);

    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    
    sort(a, a + n);
    
    scanf("%d", &m);

    for (i = 0; i < m; i++)
    {
        scanf("%d", &x);
        printf("%d\n", binary_search(a, a + n, x));
    }
}

 

배열을 입력받고 이진탐색을 빠르게 하기 위해 배열을 정렬한다. 

그리고 값을 입력받아 그 값이 배열 안에 있는지 binary_search 함수를 통해 찾는다.

scanf와 printf를 쓴 이유는 시간 초과 때문이다. iostream의 cin, cout을 쓰면 시간이 너무 오래 걸려서 시간 초과가 난다.

n, m의 범위가 100000이기 때문이다.