[백준]JAVA - 10815번: 숫자 카드

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

풀이

카운팅 정렬 형식으로 문제를 해결할 수 있지만 이분 탐색으로 분류되어 있기 때문에 이분 탐색을 이용해서 풀어보려고한다. 

 

이분 탐색은 중간 위치 값과 목표 위치 값을 비교하면서 반으로 줄여나가는 방식인데 자바에서는 메서드 하나로 귀찮은 이분 탐색 코드를 안할 수 있다. 바로 Arrays.binarySearch() 메서드인데 이분 탐색의 기본 조건과 같이 배열을 오름차순으로 정렬해주어야한다. 

 

인덱스를 반환하는 메서드로 0 이하의 값을 반환한다면 없는 것으로 간주하고 0을 출력, 0 이상의 값이 들어오면 1을 출력해서 이번 문제를 쉽게 해결할 수 있다.

자바 이분 탐색 Arrays.binarySearch() 메서드 정의 및 사용 방법

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
		
        int cnt = Integer.parseInt(br.readLine());
        int[] cards = new int[cnt];
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<cnt; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }
		
        Arrays.sort(cards);
        int m_cnt = Integer.parseInt(br.readLine());
        StringBuffer sb = new StringBuffer();
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<m_cnt; i++) {
            int m_cards = Integer.parseInt(st.nextToken());
            if (Arrays.binarySearch(cards, m_cards) < 0) sb.append("0 ");
            else sb.append("1 ");
        }
		
        bw.write(sb.toString() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}