[ JAVA / 백준 : 10815 ] 숫자 카드

조건

M개의 숫자 중 상근이가 갖고있는 카드는 1, 없으면 0출력

---

package 숫자카드;
//시간초과 - 선형탐색
//이분탐색으로 풀어야함

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

public class Main {
	public static int N;
	public static int M;
	public static int[] cards;
	public static int binarySearch(int[] cards, int N, int search) {
		int first = 0;
		int last = N - 1;
		int mid = 0;
		
		while(first <= last) {
			mid = (first + last) / 2; //중간 인덱스
			if(cards[mid] == search) {
				return 1;
			}
			if(cards[mid] < search) { // 중간값이 찾으려는 수보다 작으면
				first = mid + 1;
			} else {
				last = mid - 1;
			}
		}
		return 0;
	}
	public static void main(String[] args) throws Exception, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine()); // 카드의 개수
        int[] cards = new int[N];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(cards); // 이분탐색할 배열은 정렬되어 있어야 함.
        int M = Integer.parseInt(br.readLine()); // 구별할 수의 개수
 
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int temp = Integer.parseInt(st.nextToken());
            sb.append(binarySearch(cards, N, temp) + " ");
        }
 
        bw.write(sb.toString() + "\n");
        bw.flush();
        bw.close();
        br.close();
	}
}

Scanner로 풀었을 때는 시간초과가 나고, BufferedReader랑 Writer로 쓰니 시간초과가 안난다.. 으으

 

그래서 더 다른 해설도 찾아보았다.

값에 10,000,000을 더해서 음수값을 없애준 것이다.

 

20000001같이 큰 숫자는 1000의 단위로 _를 통해 나눌 수 있다.

import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		// 1. boolean[20_000_001]을 선언한다.
		boolean[] arr = new boolean[20_000_001];	
		
		// 2. 상근이가 가지고있는 카드의 입력을 받아서, arr[카드의 값] = true로 만들어준다.
		int n = stoi(br.readLine());
		String[] input = br.readLine().split(" ");
		for(int i = 0; i < n; i++) {
			int val = stoi(input[i]) + 10_000_000;
			arr[val] = true;
		}
		
		// 3. 구분해야 할 카드의 입력을 받아서, arr[카드의 값] == true이면 1을, 아니면 0을 출력한다.
		int m = stoi(br.readLine());
		input = br.readLine().split(" ");		
		for(int i = 0; i < m; i++) {
			int val = stoi(input[i]) + 10_000_000;
			if(arr[val]) sb.append(1);
			else sb.append(0);
			sb.append(' ');
		}
		System.out.println(sb);
	}
	public static int stoi(String str) {return Integer.parseInt(str);}
}