[백준] 10825_숫자카드 / 이진탐색 *

 

Silver

 

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

 

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

---

 

처음엔 List의 contains를 사용하여 풀이하였으나, 시간초과가 발생하였고 다른 해결방법을 구해야 했다.

 

풀이 - 이분탐색

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num1 = Integer.parseInt(br.readLine());
        int[] arr = new int[num1];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<num1; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        int num2 = Integer.parseInt(br.readLine());
        int n = 0;
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<num2; i++){
            n = Integer.parseInt(st.nextToken());
            System.out.print(binarySearch(arr, n)+ " ");
        }
        
        br.close();
    }
    public static int binarySearch(int[] arr, int n){
        int s = 0, e = arr.length-1;
        int index = 0;
        while(s<=e){
            index = (s+e)/2;
            if(arr[index] == n) return 1;
            if(arr[index] < n){
                s = index+1;
            }
            else {
                e = index-1;
            }
        }
        return 0;
    }
    
}

 

이분 탐색은 우선 정렬된 상태의 배열을 사용해야한다.

검색 범위를 절반으로 나누어 원하는 값이 어느 쪽에 있는지 판단하여 검색 범위를 좁혀 나가는 방식이다. 

 

동작 원리

1. 배열의 중간 요소를 선택한다. 
2. 중간 요소와 찾고자 하는 값을 비교한다. 
3. 검색 범위를 반복적으로 절반으로 줄이며 위 과정을 반복한다. 

시간복잡도

• 최선, 평균, 최악의 경우: O(log n)

---

 

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