[JAVA] 백준 알고리즘 10815번 (숫자 카드)

문제

---

이번에 다뤄볼 문제는 10815번 문제 '숫자 카드'입니다.

문제에서 연습해야 하는key-point는 분할정복 입니다.

 

분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘을 뜻합니다. 빠른 정렬이나 합병 정렬로 대표되는 정렬 알고리즘 문제와 고속 푸리에 변환(FFT) 문제가 대표적인 케이스 입니다.

 

이 문제는 분할정복 유형의 기초적인 예제 문제이며 다양한 구현 방식 중 이진탐색을 활용하여 해결해보겠습니다.

이진탐색(binary search)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘 입니다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식으로 탐색이 진행됩니다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 됩니다.

 

위 그림에서는 목표값 34를 이진탐색으로 찾아나가는 과정을 보여주고 있습니다.

각 단계마다 시작과 끝이 존재하고 그 중간에 위치한 값을 기준으로 목표값을 향해 탐색 범위를 좁혀가는 모습을 볼 수 있는데요.

이진탐색에서 가장 주의해야 할 점은 반드시 탐색하려는 대상이 오름차순 정렬되어 있어야 한다는 것 입니다.

정렬되어 있지 않다면 이진탐색을 사용할 수 없으며, 이런 단점을 갖고 있음에도 탐색속도가 빠르다는 장점으로 인해 자주 사용되는 탐색방식 입니다.

 

그렇다면 이제 주어진 문제를 살펴보겠습니다.

문제에서는 N개의 숫자카드와 M개의 숫자카드가 각각 주어집니다. 이때 N개의 숫자카드는 우리가 이진탐색에 활용할 대상이 되고 M개의 숫자카드는 결과를 도출해내기 위해 사용되는 대상이 됩니다.

 

따라서 N개의 숫자카드가 들어있는 배열을 입력 받고 이진탐색을 진행하기전 오름차순 정렬을 해둘 필요가 있습니다. 우리는 JAVA를 사용하여 문제를 해결하고 있기 때문에 Stream<T> sorted()를 활용하여 정렬을 진행하겠습니다.

 

정렬을 마친 후 M개의 숫자 카드를 순회하며  binarySearch() 메서드를 호출하고 원하는 숫자를 탐색한 결과에 대해 StringBuilder에 append하고 이를 최종적으로 출력하도록 하겠습니다.

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

코드(JAVA)

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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nCards = new int[n];
        for (int i = 0; i < n; i++) {
            nCards[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int[] mCards = new int[m];
        for (int i = 0; i < m; i++) {
            mCards[i] = sc.nextInt();
        }

        StringBuilder sb = new StringBuilder();
        int[] nSortedCards = Arrays.stream(nCards).sorted().toArray();
        for (int mCard : mCards) {
            if (binarySearch(nSortedCards, mCard)) {
                sb.append(1);
            } else {
                sb.append(0);
            }
            sb.append(' ');
        }
        System.out.println(sb);
    }

    private static boolean binarySearch(int[] cards, int number) {
        int start = 0;
        int end = cards.length - 1;
        int mid = (start + end) / 2;

        while (start <= end) {
            if (cards[mid] == number) {
                return true;
            } else if (cards[mid] < number) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
            mid = (start + end) / 2;
        }
        return false;
    }
}

 

10815번: 숫자 카드