[알고리즘] 백준 10815 숫자 카드 -이분탐색- 자바

 

 

 

 

www.acmicpc.net/problem/10815

10815번: 숫자 카드

 

백준 분류별 풀기에서 이분탐색문제인 숫자 카드를 풀어봤습니다. 먼저 기본적인 이분탐색문제 중 하나였습니다.

경우의 수를 보면 알다시피 보통 시간초과를 일으키는 문제라는 경고의 수인 50만개까지 데이터가 있을 수 있습니다.

 

완전탐색으로 문제를 해결하면 당연히 시간초과가 나게됩니다.

그러므로 이분탐색을 사용하여 O(N)을 O(logN) 시간복잡도를 줄여주도록 합시다. 

추가로 출력시 StringBuilder가 아닌 System.out.println을 사용해도 시간초과가 나고요.

 

풀이방법을 간략하게 설명하면,

1. 상근이 카드를 오름차순으로 정렬

2. 찾는 카드를 정렬된 상근이 배열을 이분탐색함

 

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.Arrays;
import java.util.Scanner;

class Main {
    private static int N;
    private static int[] nArr;
    private static int M;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        nArr = new int[N];
        for (int i = 0; i < N; i++) {
            nArr[i] = sc.nextInt();
        }
        Arrays.sort(nArr);
        M = sc.nextInt();
        for (int i = 0; i < M; i++) {
            int m = sc.nextInt();
            int left = 0;
            int right = N - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                int n = nArr[mid];
                if (n == m) {
                    sb.append(1 + " ");
                    break;
                }
                if (n > m) { //지금 상근이 카드보다 더 작은거 찾아야함
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
                if (left > right) {
                    sb.append(0 + " ");
                    break;
                }
            }
        }
        System.out.println(sb.toString());

    }

}