백준- 1920(수 찾기) C++

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

1920번: 수 찾기

이번 문제는 처음에 일정 개수(N)만큼 수가 주어지고, 이후에 또 다른 개수(M)만큼의 수가 주어지는데 이후에 주어지는 수들이 이전에 주어진 수들에 포함되어있는지 확인할 수 있는 코드를 짜는 것이 문제다.(있으면 1, 없으면 0)

 

그래서 필자는 우선 가벼운 마음으로 길이가 N인 배열에 처음에 주어진 수들을 하나씩 넣고, 이후에 나오는 수들을 M번 반복해 N개 배열을 0부터 N-1까지의 인덱스를 순서대로 탐색하는 선형 탐색으로 시도해봤지만....

 

살짝 예상한 결과이다...

선형 탐색을 한 코드이다.

// 선형탐색 -> 에러발생(n x m의 탐색) -> 시간복잡도가 너무 크다.

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

 

그래서 학부에서 배운 지 조금 시간이 흐른 이진 탐색을 적용해보기로 했다. (복잡도도 O(log 2 n)으로 효율적이다.)

 

우선 이진 탐색을 구현하는 조건으로 배열이 오름차순으로 정렬되어 있어야한다. 그래서 algorithm의 sort 함수를 이용해 정렬한 후 이진 탐색 기능을 하는 함수를 구현해 탐색하였다.  이진 탐색에 대한 설명은 다른 분의 블로그를 남기겠다.

 

https://jwoop.tistory.com/9

이진 탐색과 시간 복잡도 분석 (Binary Search and its Time Complexity Analysis)

 

결과 코드이다.

#include <stdio.h>
#include <algorithm>
using namespace std;

int n;

// 이분탐색
void Binary(int arr[], int d)
{
  l, r: 왼,오른쪽 기준이 되는 인덱스
  int l = 0, r = n - 1;
  
  while (l <= r)
  {
    int mid = (l + r) / 2;
    // mid가 찾는 수보다 클 때
    if (arr[mid] > d)
      r = mid - 1;
    // mid가 찾는 수보다 작을 때
    else if (arr[mid] < d)
      l = mid + 1;
    else
    {
      printf("1\n");
      return;
    }
  }
  printf("0\n");
  return;
}

int main()
{
  freopen("input.txt", "rt", stdin);
  int m;
  scanf("%d", &n);
  int arr[n];
  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }
  // 이진 탐색을 하기 위해서는 정렬을 해야 한다.
  sort(arr, arr + n);
  
  scanf("%d", &m);
  int data;
  for (int i = 0; i < m; i++)
  {
    scanf("%d", &data);
    Binary(arr, data);
  }

  return 0;
}

통과!

 

구글링을 통해 다른 사람들의 결과를 살펴보니, 이렇게 함수를 직접 구현하지 않고, algorithm의 binary_search를 이용해 이진탐색을 수행할 수 있는 함수가 있었다..... 이 방법 역시 통과되었다. 이를 활용하면 더 편리하게 풀 수 있을 것 같다!

 

#include <stdio.h>
#include <algorithm>
using namespace std;

int main()
{
  freopen("input.txt", "rt", stdin);
  int n, m;
  scanf("%d", &n);
  int arr[n];
  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }
  sort(arr, arr + n);
 
  scanf("%d", &m);
  int data;
  for (int i = 0; i < m; i++)
  {
    scanf("%d", &data);
    // Binary(arr, data);

    // 내장함수
    if (binary_search(arr, arr + n, data))
      printf("1\n");
    else
      printf("0\n");
  }

  return 0;
}

오늘 이 문제를 통해 이진 탐색에 대해 복습할 수 있는 기회가 되었고, 앞으로 문제풀이들을 통해 잊고 있던 지식들을 빨리 다시 되찾아야겠다....