자바로 백준 1270 풀기

• 실버 4단계 문제

풀이)
N개의 정수들 중 원하는 수를 찾아야 한다. 숫자는 최대 10만개이며,
정수는 2^31 이하이다.
int 는 4바이트 = 4 x 8비트 = 32비트, 즉 2^32만큼의 크기를 표현할 수 있다.
따라서 int는 -2^31~2^31의 크기가 가능하니,
여기서 입력받는 수를 int형으로 받아도 된다.

숫자를 정렬할 때 O(nlogn)을 사용해도 되므로, 자바 내부 함수를 사용할 것.
숫자를 찾을 때 O(nlogn)을 사용해도 되므로, 이진 탐색 방법을 사용할 것.

그리고 숫자를 그대로 System.out.print 하는 것보다, StringBuilder을 쓰는게 훨씬 시간 단축이 된다.
위는 StringBuilder을 사용했고, 아래는 사용하지 않은 코드.

내 코드)

// 백준 온라인 저지 1920번

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

public class Main{
	static int arr[];
	static int bin_search(int num) {
		int low = 0, high = arr.length-1;
		int mid;
		while(low<=high) {
			mid = (low+high)/2;
			
			if(num == arr[mid]) {
				return 1;
			}else if (num < arr[mid])
				high = mid-1;
			else
				low = mid+1;
		}
		return 0;
	}
	
	public static void main(String[]args) throws IOException{
		
		// 입력. 
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bf.readLine());
		arr = new int[N];
		StringTokenizer st = new StringTokenizer(bf.readLine());
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int M = Integer.parseInt(bf.readLine());
		int ans[] = new int[M];
		st = new StringTokenizer(bf.readLine());
		for(int i=0;i<M;i++) {
			ans[i] = Integer.parseInt(st.nextToken());
		}
		
		// 정렬.
		Arrays.sort(arr);

		// 이진 탐색.
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<M;i++) {
			sb.append(bin_search(ans[i]));
			sb.append("\n");
		}		
		System.out.println(sb);
	}
}