백준 1920번 자바

문제

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

1920번: 수 찾기

 

1. 이진탐색? 이분탐색?

이진, 이분 탐색 둘다 의미는 비슷하기에 크게 구분하지 않아도 된다.

 

이진 탐색 : 찾으려는 값(a)가 배열(arr)에 존재하는지 찾을 때 arr의 중간값과 비교를 하면서 탐색하는 방법이다.

 

예를 들어 

찾으려는 값(a)이 2라고 할때, 아래 배열(arr)의 중간값(mid)인 4와 비교를 한다.

1

2

3

4

5

6

7

8

a < mid 이기 때문에 아래와 같이 arr[0]~arr[2] 에서만 탐색을 진행한다.

1

2

3

이런 식으로 계속 탐색을 하다 같은 값을 찾을 때와 못 찾을 때를 어떻게 처리할지 생각해야한다. 보통 값을 찾으면 1을 반환, 못 찾으면 -1을 반환하는 식으로 구현한다.

 

제일 중요한것은 이진 탐색은 정렬된 배열에서만 사용 가능하다는 점이다.

 

2. 구현

병합정렬을 다시 공부할 겸 Arrays.sort를 사용하지 않고 구현해봤다. 시간초과가 날줄 알았지만 다행히도 정답처리 됐다.

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

public class Main1920 {

	static int N,M;
	static int[] arr;
	static int[] temp;
	static int[] checkNum;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		temp = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		M = Integer.parseInt(br.readLine());
		checkNum = new int[M];
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<M; i++) {
			checkNum[i] = Integer.parseInt(st.nextToken());
		}
		
		mergeSort(0, N-1);
		
		for (int i=0; i<M; i++) {
			binarySearch(checkNum[i], 0, N-1);
		}
	}
	
	public static void mergeSort(int start, int end) {
		int mid = start + (end-start)/2;
		
		if (end-start > 0) {
			mergeSort(start, mid);
			mergeSort(mid+1, end);
		}
		
		for (int i=start; i<=end; i++) {
			temp[i] = arr[i];
		}
		int i = start;
		int j = mid+1;
		int k = start;
		while (i <= mid && j <= end) {
			if (temp[i] > temp[j]) {
				arr[k] = temp[j];
				k++;
				j++;
			} else {
				arr[k] = temp[i];
				k++;
				i++;
			}
		}
		
		while (i <= mid) {
			arr[k] = temp[i];
			k++;
			i++;
		}
		while (j <= end) {
			arr[k] = temp[j];
			k++;
			j++;
		}
	}
	
	public static void binarySearch(int checkNum, int start, int end) {
		int mid = start+(end-start)/2;
		
		if (checkNum == arr[mid]) {
			System.out.println(1);
			return;
		}
        // 위 조건문에서도 일치하지 않는다면 일치하는 값이 없기때문에 메소드를 종료한다.
		if (end-start <= 0) {
			System.out.println(0);
			return;
		}
		if (checkNum < arr[mid]) {
			binarySearch(checkNum, start, mid-1);
		} else if (checkNum > arr[mid]){
			binarySearch(checkNum, mid+1, end);
		} 	
	}
}

 

정리 : 입력과 마찬가지로 출력도 System.out.println을 쓰면 속도가 많이 떨어진다. 가급적 StringBuilder를 사용해 한 번에 출력하거나 BufferedWriter를 사용하도록 하자.