[백준풀이, 병합정렬, 이분탐색 개념정리] 백준10815 해쉬안쓰고 이분탐색 병합정렬 사용(자바)

전체 코드

package baek_10815;

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

public class Numcard 
{
	public static void main(String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		int N = Integer.parseInt(br.readLine());
		int[] input = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++)
		{
			input[i] = Integer.parseInt(st.nextToken());
		}
		int[] result =mergesort(input);
		
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		int finder;
		StringBuilder sb =new StringBuilder();
		for(int i=0;i<M;i++)
		{
			finder = Integer.parseInt(st.nextToken());
			if(BinarySearch(result, finder)!=-1)
			{
				sb.append(1+" ");
			}
			else
			{
				sb.append(0+" ");
			}
		}	
		System.out.println(sb);
		
		
	}
	
	private static int BinarySearch(int[] arr, int target)
	{
		int left =0;
		int right= arr.length-1;
		int mid;
		
		while(right>=left)//left right같을때가 target값을 찾을때이다. 
		{
			mid= (left+right)/2;
			/*System.out.printf("arr[left]: %d   arr[mid]: %d   arr[right]: %d", arr[left],arr[mid],arr[right]);
			System.out.println();*/
			if(target>arr[mid])
			{
				left= mid+1;
			}
			else if(target<arr[mid])
			{
				right = mid-1;
			}
			else//(target==arr[mid])
			{
				return mid;
			}
		}
		return -1;
	}
	public static int[] mergesort(int[] arr)
	{
		if(arr.length<2)return arr;//재귀 종료
		
		int mid = (arr.length)/2;
		//원소가 2개 남았을때 0인덱스와 1인덱스 배열이 각각 하나씩 생성되고 재귀호출후 바로 리턴
		int[] low_arr = mergesort(Arrays.copyOfRange(arr,0,mid));//0<= && <mid
		int[] high_arr = mergesort(Arrays.copyOfRange(arr, mid, arr.length));
		int[] result_arr = new int[arr.length];
		int idx0=0, idx1=0, idx2=0;
		
		while(idx1<low_arr.length&& idx2<high_arr.length)
		{
			//각각 소배열의 인덱스가 가르키는 배열요소끼리 비교
			if(low_arr[idx1]<high_arr[idx2])
			{
				result_arr[idx0++] = low_arr[idx1++]; 
			}
			else
			{
				result_arr[idx0++] = high_arr[idx2++];
			}
		}
		
		while(idx1<low_arr.length)
		{
			result_arr[idx0++] = low_arr[idx1++];
		}
		while(idx2<high_arr.length)
		{
			result_arr[idx0++] = high_arr[idx2++];
		}
		return result_arr;
	}
	
}

병합정렬 시간복잡도 : O(NlogN)

이분탐색 시간복잡도 : O(logN)

병합정렬

정렬하고자 하는 배열을 받아서 중앙 인덱스를 기준으로 두개의 배열을 나눈다.
그리고 그 나눈 배열을 mergesort에 넣어 호출한다(재귀) 이러한 재귀는 mergesort의 맨 처음 구문에 의해 종료된다.

if(arr.length<2)return arr;//재귀 종료

그림으로 보면 이렇다 low_arr, high_arr 요소가 각각1개가 되면 mergesort 코드 실행하지 않고 반환한다. 반환되면 작은배열들이 정렬되고 다시 큰배열이 정렬되는게 반복된다

이분탐색

이분탐색은 간단하다. 배열 크기가 짝수가 되면 mid값이 중앙에서 하나 작은값이 되는게 특이점(무시해도된다)

정리

1. binary sort는 찾고자하는 배열이 정렬되어야 쓸 수 있다.
2. 공부할때만 직접 구현해보고 실제 개발에서는
   Arrays.sort() / Arrays.binarySearch() 쓰자 ㅋㅋ