10815

숫자카드 : https://www.acmicpc.net/problem/10815

 

입력이 1천만 정도로 int의 최고값에 미치지 못하므로 넉넉한 메모리를 활용하여

간단하게 풀이 가능함. 

시간 676ms 

메모리 : 153,368KB => boolean 배열을 활용하는데 20MB를 사용함

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main {

	static int N, M;
	static boolean DBG = false;	
	static boolean[] ar;
	static int MAX = 10000000;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		N = Integer.parseInt(br.readLine());

		ar = new boolean[2 * MAX + 1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			ar[Integer.parseInt(st.nextToken()) + MAX] = true;
		}

		M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			sb.append(ar[Integer.parseInt(st.nextToken()) + MAX] ? 1 : 0).append(' ');
		}

		System.out.println(sb);

	}

}

 

 

이문제가 이분탐색의 항목에 있는 이유를 몰라 검색을 해보니..

아래와 같은 방식으로 코드를 구현해 놓은게 있다.

 

https://dragon-h.tistory.com/30

 

이진 탐색을 통한 포함 유무 확인 방법 

시간: 1048ms

메모리 : 135,300KB

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

	static int N, M;
	static boolean DBG = false;
	static int[] arr;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());

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

		Arrays.sort(arr);
		
		M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			boolean res = binarySearch(arr, Integer.parseInt(st.nextToken()));
			bw.write(res ? "1 " : "0 ");
		}

		br.close();
		bw.close();

	}

	static boolean binarySearch(int[] list, int target) {
		int lt = 0;
		int rt = list.length - 1;
		boolean result = false;
		while (lt <= rt) {
			int mid = (rt + lt) / 2;
			if (list[mid] > target) {
				rt = mid - 1;
			} else if (list[mid] < target) {
				lt = mid + 1;
			} else {
				result = true;
				break;
			}

		}
		return result;
	}

}