[Java] 백준 10815 숫자 카드

 

문제

상근이가 가진 숫자카드 N개가 주어지고, 각각의 카드에는 -10,000,000 이상 10,000,000 이하의 정수가 적혀있다.

그 다음 M개의 정수가 주어질 때 상근이가 가지고 있는 숫자인지를 판별해서 출력하는 문제이다.

 

 

2가지 방식으로 풀이했다.

1) 배열로 방문체크

- 카드가 가질 수 있는 숫자의 범위만큼 boolean배열을 만든다.

- 상근이가 가지고 있는 숫자라면 해당 인덱스의 값을 true로 초기화한다.

- M개의 카드 인덱스를 받아와서 boolean배열의 값이 true인지 확인한다.

 

2) 이진탐색

- 상근이가 가진 카드 배열을 오름차순 정렬한다.

- M개의 카드 값을 받아와서 상근이의 카드배열을 이진탐색한다.

 

 

 

코드

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

public class Main {

    // 1) 방문배열로 체크
    static void solution1() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        boolean[] isPresent_m = new boolean[10_000_001];
        boolean[] isPresent_p = new boolean[10_000_001];

        for (int i = 0; i < N; i++) {
            int idx = Integer.parseInt(st.nextToken());
            if (idx >= 0) isPresent_p[idx] = true;
            else isPresent_m[-idx] = true;
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int idx = Integer.parseInt(st.nextToken());
            if (idx >= 0) {
                if (isPresent_p[idx]) sb.append(1).append(" ");
                else sb.append(0).append(" ");
            } else {
                if (isPresent_m[-idx]) sb.append(1).append(" ");
                else sb.append(0).append(" ");
            }
        }

        System.out.println(sb);
    }

    // 2) 카드배열을 이진탐색
    static int[] cards;
    static void solution2() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        cards = new int[N];
        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(cards);

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

        for (int i = 0; i < M; i++) {
            int target = Integer.parseInt(st.nextToken());
            sb.append(binarySearch(0, N - 1, target)).append(" ");
        }
        System.out.println(sb);
    }


    static int binarySearch(int low_idx, int high_idx, int target_value) {
        if (high_idx < low_idx) // 등호 x
            return 0;

        int mid_idx = (low_idx + high_idx) / 2;
        if (cards[mid_idx] > target_value) {
            return binarySearch(low_idx, mid_idx - 1, target_value);
        } else if (cards[mid_idx] < target_value) {
            return binarySearch(mid_idx + 1, high_idx, target_value);
        } else
            return 1;
    }


    public static void main(String[] args) throws IOException {
//        solution1();
        solution2();
    }
}

 

 

 

 

채점결과

위: 방문배열 풀이

아래: 이진탐색 풀이