백준[1920]번: 수 찾기 ( JAVA )

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

1920번: 수 찾기

---

Code

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

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));
		
		int n = Integer.parseInt(br.readLine());
		
		ArrayList<Integer> list = new ArrayList<>();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i=0;i<n;i++) {
			list.add(Integer.parseInt(st.nextToken())); 
		}
		
		Collections.sort(list);
		int[] arr = new int[n];
		
		for(int i=0;i<n;i++) {
			arr[i] = list.get(i);
		}
		
		int m = Integer.parseInt(br.readLine());
		
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		
		for(int i=0;i<m;i++) {
			bw.write(Binary(arr,Integer.parseInt(st1.nextToken()),0,n-1)+"\n");
		}
	
		br.close();
		bw.close();
	}
	public static int Binary(int[] arr,int key,int low,int high) {
		
		if(low > high) {
			return 0;
		}
		int mid = (low+high) / 2;
		
		if(arr[mid] == key) {
			return 1;
		}
		else if(arr[mid] < key) {
			return Binary(arr,key,mid+1,high); 
		}
		else{
			return Binary(arr,key,low,mid-1);
		}
	}
}

---

처음 문제풀이는 List를 이용하여 기본값들을 받고 contains메서드를 이용해서 1 또는 0이 출력되게 했다.

제출 시 시간초과가 났고 이분탐색을 사용해야한다는 것을 알았다.

 

이분탐색 자료구조는 특정 요소를 찾을 때 쓰인다.

주어진 배열을 정렬시키고 배열을 계속해서 반씩 나누어 탐색하는 방법이다.

 

https://qkrehdwns032.tistory.com/40

이분 탐색,이진 탐색(Binary Search) 알고리즘에 대해 알아보자. ( Java )

이 문제를 통해 이분탐색에 대해 정리해 둔 글이 있으니 보면 바로 이해가 갈 것이다.