알고리즘 풀이 - 백준 10815(숫자 카드, 분할정복)

 

관련글

 

분할정복 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

정수 하나가 적힌 카드 N개를 갖고 있고, 정수 M개가 주어질 때, M개의 정수 중 카드에 적힌 숫자를 가진 경우 해당 숫자는 1로, 아닌 경우는 0으로 출력하는 문제

 

 

2. 풀이

 

간단한 분할정복 문제이다. 개념은 다음과 같다. 숫자가 적힌 카드 1, 2, 4가 다음과 같이 있고 주어지는 M개의 숫자를 4, 5, 6, 7 이라고 하자.(M=4라고 가정)

 

그러면 다음과 같을 것이다.

 

상단의 네모가 카드, 아래 동그라미가 주어진 M개의 숫자라고 하자.

숫자 4만 카드에 있는 숫자이므로 정답은 [ 1 0 0 0 ] 이 된다.

 

어떻게 분할정복으로 해결할 수 있을까?

우선 주어진 카드를 숫자 순서대로 정렬하고 M개의 숫자를 반복문을 통해 돌리면서 이분탐색을 수행하여 숫자가 있는지 여부를 찾으면 된다.

이분(이진) 탐색은 대표적인 분할정복 방식의 알고리즘이다. 관련 내용은 여기를 참조한다.

 

 

사실 이 문제는 분할정복이 아니라 단순히 배열의 index를 이용해서도 해결이 가능하다.(훨씬 더 빠르게 해결 가능)

그 방법 또한 아래에서 코드로 알아보자.

 

 

3. 코드

 

이분 탐색을 통해 해결하는 방법을 아래의 코드를 통해 정답을 알아보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
    static int[] card;
    static int[] nums;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        card = new int[n];

        // 카드로 나온 숫자를 입력 받고 정렬한다.
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i < n; i++){
            card[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(card);

        // 주어진 m개의 카드를 입력 받는다.
        int m = Integer.parseInt(br.readLine());
        nums = new int[m];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i < m; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }

        // 각 주어진 숫자를 이진 탐색으로 찾아서 있으면 1, 없으면 0으로 표기한다.
        StringBuilder sb = new StringBuilder();
        for(int i=0; i < m; i++){
            if(binarySearch(nums[i])){
                sb.append(1);
            } else {
                sb.append(0);
            }
            sb.append(" ");
        }
        System.out.println(sb);
        br.close();
    }

    // 이분탐색(분할정복)을 통해 숫자가 있는지 확인하는 메소드
    private static boolean binarySearch(int num){
        int start = 0;
        int end = card.length - 1;
        int mid = (start+end)/2;

        while(start <= end){
            // 숫자가 있으면 true 반환
            if(card[mid] == num) {
                return true;
            } else if(card[mid] < num){
                start = mid+1;
            } else {
                end = mid-1;
            }
            mid = (start + end) / 2;
        }
        return false;
    }
}

 

 

분할정복 방식이 아니라 단순히 배열 위치를 통해서도 해결할 수 있다.

해당 코드는 아래에서 확인하자.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 2천만 1 크기의 배열 생성
        int[] cards = new int[20000001];
        for(int i=0; i < n; i++){
            int c = Integer.parseInt(st.nextToken());
            
            // -1천만 ~ 1천만이므로, 배열에 0부터 저장하기 위해 1천만을 각각 더해서 저장
            cards[c+10000000] = 1;  
        }

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        StringBuilder sb = new StringBuilder();
        for(int i=0; i < m; i++){
            int num = Integer.parseInt(st.nextToken());
            
            // 1천만을 더한 위치에 1이 들어가 있다면 해당 숫자가 카드로 있는 것임!
            if(cards[num+10000000] == 1) sb.append(1).append(" ");
            else sb.append(0).append(" ");
        }

        System.out.println(sb);
        br.close();
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.