[백준] 1920 수 찾기 (Java/Python)

1920번: 수 찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다.

 

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

제한

• 1 ≤ N, M ≤ 100,000
• -2^31 ≤ A, M개의 수 < 2^31

 

---

접근 방식

문제 이해

주어지는 M개의 숫자가 N개의 숫자 안에 존재하는지 판단해라.

• 존재: 1
• 존재 X: 0

 

접근

이분 탐색 알고리즘을 알고 있다면 바로 해결이 가능하다.

[Algorithm] Binary Search (이분 탐색)

 

시간 복잡도

M개의 수에 대하여 이분 탐색 실행

M x O(logN) → O(MlogN)

 

Code

코드를 보기 전에 스스로 구현해 보는 것을 권장합니다.

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_1920 {
    public static boolean binarySearch(int[] arr, int x){
        int lo=0, hi=arr.length-1;

        while(lo <= hi){
            int mid=(lo+hi)/2;

            if(x < arr[mid]){
                hi = mid-1;
            }
            else if(x > arr[mid]){
                lo = mid+1;
            }
            else{
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N, M;

        N = Integer.parseInt(bf.readLine());
        int[] arr = new int[N];

        StringTokenizer st = new StringTokenizer(bf.readLine());

        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        M = Integer.parseInt(bf.readLine());
        st = new StringTokenizer(bf.readLine());

        for(int i=0; i<M; i++){
            int x = Integer.parseInt(st.nextToken());
            if(binarySearch(arr, x))
                sb.append(1 + "\\n");
            else
                sb.append(0 + "\\n");
        }

        System.out.print(sb);
    }
}

Python

#1920 수 찾기
'''
  1. 시간 초과 - in을 이용한 단순 연산 - O(N*M)
  2. 정렬 후 이진 탐색 - O((N+M)logN)
'''
import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))
nums.sort()

m = int(input())
find_nums = list(map(int, input().split()))

def findNum(num):
  lo, hi = 0, len(nums)-1
  while lo <= hi:
    mid = (lo + hi) // 2

    if nums[mid] < find_num:
      lo = mid + 1
    elif nums[mid] > find_num:
      hi = mid - 1
    else:
      return True
  return False

for find_num in find_nums:
  print(1 if findNum(find_num) else 0)