[백준] JAVA - 1920.수 찾기

생각

N,M이 모두 10만이기 때문에 단순히 이중포문으로 문제를 풀면 100억이 나오게 됩니다. 따라서 logN 정도의 시간복잡도를 가지게끔 낮춰야합니다. logN의 시간복잡도를 가지는 이진탐색으로 문제를 풀었습니다. (한번 비교가 일어날때마다 리스트가 반씩 줄어들기 때문에 logN의 시간복잡도를 가집니다.)

 

M개의 배열을 돌면서 각각의 원소들이 주어진 배열안에서 존재하는지 찾아야하므로 총 시간 복잡도는 MlogN을 가지게 됩니다.

 

이진탐색을 구현할때 먼저 찾으려는 배열은 정렬되어있어야 하기 때문에 origin 배열을 Array.sort를 사용하여 정렬했습니다. 그 다음, 배열의 중간값을 설정하고 중간보다 작은 값이면 왼쪽을 탐색하고 큰 값이라면 오른쪽을 탐색하는 반복문을 통해 이진탐색을 구현했습니다.

 

이진탐색 알고리즘

1. 찾으려는 배열 정렬
2. 중간값이 찾으려는 target 이라면 값을 찾고 return
3. 중간값보다 찾으려는 값이 작다면 rightIdx = mid-1
4. 중간값보다 찾으려는 값이 크다면 leftIdx = mid+1

Java code

package com.java.algorithm;

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

public class Baekjoon_1920_수찾기 {
	static int[] origin;
	static int[] target;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		origin = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for (int i = 0; i < N; i++) {
			origin[i] = Integer.parseInt(st.nextToken());
		}
		
		int M = Integer.parseInt(br.readLine());
		target = new int[M];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < M; i++) {
			target[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(origin);
		for (int i = 0; i < M; i++) {
			binarySearch(target[i]);
		}
		
	}

	private static void binarySearch(int item) {
		//이분탐색 
		int left=0;
		int right=origin.length-1;

		while (left <= right) {
			int mid = (left+right)/2;
			if(origin[mid] == item) {
				System.out.println(1);
				return;
			}else if(origin[mid] > item) {
				right = mid-1;
			}else {
				left = mid+1;
			}
		}
		System.out.println(0);
		return;
			
		
	}

}