[JAVA] 백준 1920 - 수 찾기

실버 IV

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

1920번: 수 찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

---

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

---

접근방법

이분탐색을 이용하여 숫자를 탐색하였다.

---

코드

package bj1920;

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

public class bj1920 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//입력할 숫자 개수 입력
		int num = Integer.parseInt(br.readLine());
		int[] n = new int[num];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		//숫자 입력
		for(int i = 0; i < num; i++)
			n[i] = Integer.parseInt(st.nextToken());
		
		Arrays.sort(n); //오름차순 정렬
		
		//찾을 숫자 개수 입력
		num = Integer.parseInt(br.readLine());
		int find = 0;
		int[] check = new int[num];
		st = new StringTokenizer(br.readLine(), " ");
		
		//찾을 숫자 입력
		for(int i = 0; i < num; i++) {
			find = Integer.parseInt(st.nextToken());
			check[i] = binarySort(n, find); //이진탐색 결과 저장
		}
		
		//결과 출력
		for(int i = 0; i < num; i++)
			System.out.println(check[i]);
	}
	
	//이진탐색
	public static int binarySort(int array[], int target) {
		
		int start = 0; //시작인덱스
		int end = array.length - 1; //끝 인덱스
		int mid = (start + end) / 2; //중간 인덱스
		
		while(end - start >= 0) {
			
			if(array[mid] == target) 
				return 1; //배열에 찾을 숫자가 있다면 1반환
			
			else if(array[mid] <= target)
				start = mid + 1;
			
			else
				end = mid - 1;
			
			mid = (start + end) / 2;
		}
		
		return 0; //배열에 찾을 숫자가 없다면 0반환
	}

}

---

NOTE

StringTokenizer st = new StringTokenizer(br.readLine(), " ")를 사용할 때 사용할 변수 바로 위에 위치시켜야 한다.

또한 이진탐색을 하기 위해서는 배열을 꼭 오름차순으로 정렬하고 사용해야한다.