[백준,BOJ 11004] k번째 수( JAVA 구현)

-내 생각

  우선 이 문제를 보면, 단순하게 자바에서 제공하는 Arrays.sort()를 이용하여 정렬 후 k번 째 수를 출력하면 되는 간단한 문제라고 생각했다. 그러나 결과는 시간 초과가 발생하였고, 입력 값의 수가 많기 때문에 BuffredReader 클래스를 사용하여서 StringTokenizer을 통해 공백을 구분하여 입력받아 제출해보았지만, 역시 시간 초과가 발생하였다. 그래서 검색을 통해 찾아보았더니 이러한 N개의 수에서 K번 째 수를 반환하는 경우에 사용되는 특정한 알고리즘인 Quick Selection이라는 알고리즘이 존재한다는 사실을 알 수 있었고, 해당 알고리즘은 Quick sort방식을 응용한 방식이라는 점을 알게 되어서, 우선 Quick sort문제를 풀면서 공부하기로 한 이후 미루어 놓은 문제였다. 

 

-해법

  기본적인 원리는 우리가 평소 Quick sort를 사용할 시 설정한 pivot의 자리가 설정(partition 과정)되면 이후 두 개의 부분집합으로 나눈 후 정렬하는 분할 정복 방식을 응용한 것으로, Quick sort의 과정으로 결정된 pivot의 자리값과 입력받은 k값을 비교해 해당하는 부분만 계속해서 분할 정복해 나가는 방식이다. 이를 그림으로 표현해보면, 아래와 같다.

 

 

  초기 입력이 배열에 들어오면 우선적으로 Quick Sort를 통해 첫 번째로 고정된 pivot의 위치를 통해 k와 값을 비교한다. 위 이미지에서 고정된 1번 idx의 경우 배열의 인덱스를 0번부터 사용했기 때문에 K의 입력이 2라고 가정 한다면 더 이상의 정렬을 진행할 필요 없이 종료하고 출력하면 된다. 즉, 1+1 ==K인 경우이다. 그러나 K의 입력이 1이라고 가정할 경우, 0번 인덱스가 정렬을 통해 pivot으로 고정이 되어야 한다. (그림상으로는 현재 0번 인덱스 한 개 밖에 존재하지 않기 때문에 정렬되어 있다고 생각할 수 있지만) 왼쪽 부분집합을 대상으로 Quick Sort를 재귀 호출하여 처리해 줄 필요가 있다. 대신, 1번 인덱스의 오른쪽 부분집합인 2번, 3번, 4번 인덱스의 경우는 pivot에 고정된 값 보다 모두 큰 값들만 존재하기 때문에, 더 이상의 정렬은 필요 없기 때문에 고려하지 않게 되는 것이다. (반대의 경우도 마찬가지)

 

  최종적으로 위와같은 방식으로 고정된 pivot 즉, partition을 통해 왼쪽 오른쪽 부분집합으로 나누어 k가 속하는 부분집합에 대해서만 Quick Sort를 수행하면 모든 데이터를 정렬할 필요가 없이 문제를 해결할 수 있는 것이다.

 

+) 추가적으로 Qucik Sort알고리즘에 대해 알고 싶은 분은 해당 글을 참고하길 바란다.

https://fbtmdwhd33.tistory.com/85

[백준,BOJ 2751] 수 정렬하기 2( JAVA 구현)

 

import java.util.*;
import java.math.*;
import java.io.*;

public class Main  {
	
	 	static int k,n;
		public static int partition(int[] array, int left, int right) {
		    int mid = (left + right) / 2; 
		    swap(array, left, mid); // 중앙 값을 첫 번째 요소로 이동
		 
		    int pivot = array[left];
		    int i = left, j = right;
		 
		    while (i < j) {
		        while (pivot < array[j]) { // j는 오른쪽에서 왼쪽으로 피봇보다 작거나 같은 값을 찾는다.
		            j--;
		        }
		 
		        while (i < j && pivot >= array[i]) { // i는 왼쪽에서 오른쪽으로 피봇보다 큰 값을 찾는다.
		            i++;
		        }
		        swap(array, i, j); // 찾은 i와 j를 교환
		    }
		    // 반복문을 벗어난 경우는 i와 j가 만난경우
		    // 피봇과 교환
		    array[left] = array[i];
		    array[i] = pivot;
		    return i;
		}
		 
		public static void swap(int[] array, int a, int b) {
		    int temp = array[b];
		    array[b] = array[a];
		    array[a] = temp;
		}
		 
		public static void quicksort(int[] array, int left, int right) {
		    if (left >= right) {
		        return;
		    }
		 
		    int pi = partition(array, left, right);
		    
		   // partition과정을 통해 구한 구분점에 +1한 값과 k를 비교하여 해당하는 부분집합에 대해
           // 재귀호출을 반복한다.
		    if(pi+1 == k) return;
		    else if(pi+1<k)
		    	quicksort(array, pi + 1, right);
		    else
		    	quicksort(array, left, pi - 1);
		    
		}


		
		public static void main(String[] args) throws IOException {
			 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			 StringTokenizer st = new StringTokenizer(br.readLine());
			 
			 n =Integer.parseInt(st.nextToken());
			 k = Integer.parseInt(st.nextToken());
			 int arr[] = new int[n];
			 
			 st = new StringTokenizer(br.readLine());
			 for(int i=0;i<n;i++) {
				 arr[i] = Integer.parseInt(st.nextToken());
				 
			 }
			 
			 quicksort(arr,0,n-1);
		       
			 System.out.println(arr[k-1]);
		     
			
				
		       
		}
	
}