[백준] 10815 - 숫자카드

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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을 공백으로 구분해 출력한다.

 

주어진 숫자 카드가 갖고 있는 카드인지 판단하는 문제이므로 이진탐색을 활용하여 문제를 풀어보았다.

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[] cards = new int[N];

        for (int i = 0; i < N; i++) {
            cards[i] = sc.nextInt();
        }

        Arrays.sort(cards);

        int M = sc.nextInt();
        int[] targets = new int[M];

        for (int i = 0; i < M; i++) {
            targets[i] = sc.nextInt();
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <M; i++) {
            if (binarySearch(cards, targets[i])) {
                sb.append("1 ");
            } else {
                sb.append("0 ");
            }
        }

        System.out.println(sb.toString().trim());

        sc.close();
    }

    public static boolean binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (array[mid] == target) {
                return true;
            } else if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

코드를 보면, binarySearch라는 함수를 따로 작성해주어서 이진탐색 함수를 작성해주었다.

이진탐색 함수는 탐색 범위를 나타내는 양쪽 끝 값으로 left, right 변수를 각각 만들어주고 그 가운데의 범위에 해당하는 min변수를 만들어준다. 이 중간값이 target(찾고자 하는 값)과 같다면 탐색을 완료하고 중간값이 target보다 작다면 left를 mid+1로 설정하여 오른쪽 부분에서 다시 탐색을 시작한다. 마찬가지로 중간값이 target보다 크다면 right를 min-1로 설정하여 왼쪽 부분에서 다시 탐색을 시작한다. left가 right보다 커지면 탐색 범위가 사라진 것 이므로 그 때 탐색을 종료해주고 false를 출력해주면 된다.

 

이 함수를 활용하는 과정에서 StringBuilder이라는 자바에서 제공하는 클래스를 사용하였는데 자세히 코드를 한번 보자.

StringBuilder sb = new StringBuilder();
        for (int i = 0; i <M; i++) {
            if (binarySearch(cards, targets[i])) {
                sb.append("1 ");
            } else {
                sb.append("0 ");
            }
        }

        System.out.println(sb.toString().trim());

 

반복문을 통해 두 번째 배열(targets)의 각 i번째 요소에 대해 binarySearch함수를 호출하여 해당 i번째 요소가 첫 번째 배열에 존재하는지 확인해준다. 그리고 만약에 존재한다면 StringBuilder객체에 생성된 sb라는 변수에 1을 추가해주고 아니라면 0을 추가해준다. 마지막 출력문에서는 이전시간에 다루었던 trim을 활용해 끝에 생기는 공백을 지워주었다.