(Java)백준 24060 알고리즘 수업 - 병합 정렬 1

 

1. 문제 조건

문제 제목 그대로 주어진 수를 병합정렬을 이용해 푸는 문제.

숫자를 정렬 할 때마다 개수를 세서, K번째 정렬한 숫자를 출력해야 한다.

 

2. 아이디어

구현해놓은 병합 정렬을 활용하기

단, 전체를 정렬할 필요 없이, 문제의 조건이 충족되는 순간 모든 메서드를 멈추고 결과값을 출력해봤다.

 

3. 구현

package Silver4;

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

public class Main_24060병합정렬1 {
	
	static int[] arr;
	static int[] result;
	static int N;
	static int cnt;
	static int K;
	static int answer;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		arr = new int[N];
		result = new int[N];
		cnt =0;
		answer = -1;
		
		st = new StringTokenizer(br.readLine());
		for(int t=0; t<N; t++) {
			arr[t] = Integer.parseInt(st.nextToken());
		}
		merge_sort(arr, 0, N-1);
		
		
		System.out.println(answer);


	}
	public static void merge_sort(int[]arr, int left, int right) {
		//기저부분
		//left와 right가 같아지거나 자리가 바뀌는경우(추월?되는경우!) 메서드 종료
		if(left>=right) return;
		
		//분할과정
		merge_sort(arr, left, (left+right)/2);	 //왼쪽
		merge_sort(arr, (left+right)/2+1, right);//오른쪽
		
		//합치기
		merge(arr, left, right);
		
	}
	
	
	public static void merge(int[] arr, int left, int right) {
		int m = (left+right)/2 ;
		int i = left;
		int j = m+1;
		int idx = left;
		
		//왼쪽 배열의 포인터와 오른쪽 배열의 포인터가 각각 나누어진 배열 범위 내일 때
		while(i<=m && j<=right) {
			//왼쪽 배열의 값이 더 작으면 왼쪽 배열 값을 result배열에 넣은 후 idx ++, i++
			if(arr[i]<=arr[j]) {
				result[idx++] = arr[i];
				cnt ++;
				i++;
			//오른쪽 배열의 값이 더 작으면 오른쪽 배열 값을 넣기
			}else {
				result[idx++] = arr[j];
				j++;
				cnt++;
			}
		//문제의 조건 (K번째 넣은 값 찾기)에 충족되면 방금 전에 result에 넣은 값을 answer에 넣고 break;
		//이 문제는 정렬 과정에서 해당 순서만 원하므로 끝까지 정렬할 필요는 없음
		if(cnt ==K) {
			answer = result[idx-1];
			break;
		}

			
		}
		//cnt가 원하는 조건이 되지 않았다면 마저 정렬을 계속하기
		if(cnt!= K) {
		//왼쪽 배열의 수가 남아있다면 왼쪽 배열 값을 result에 넣기. 
		//이 때도 result에 값을 넣은 것이므로 cnt++하고 조건 충족됐는지 체크
		for(int k=i; k<m+1; k++) {
			result[idx++] = arr[k];
			cnt ++;
			if(cnt ==K) {
				answer = result[idx-1];
				break;
			}
		}
		//오른쪽 배열의 숫자가 남아있을 때.
		for(int k=j; k<=right; k++) {
			result[idx++] = arr[k];
			cnt++;
			if(cnt ==K) {
				answer = result[idx-1];
				break;
			}
		}
		//원래 배열에 넣어 씌우기
		for(int k=left; k<=right; k++) {
			arr[k] = result[k];
		}
		
		}
	}
}