관리 메뉴

막내의 막무가내 프로그래밍 & 일상

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

알고리즘/이분탐색

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

막무가내막내 2021. 2. 28. 16:32
728x90

 

 

 

 

www.acmicpc.net/problem/10815

 

10815번: 숫자 카드

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

www.acmicpc.net

 

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

경우의 수를 보면 알다시피 보통 시간초과를 일으키는 문제라는 경고의 수인 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());

    }

}

 

728x90
Comments