[백준]S5_11004_K번째 수

백준 S5_11004_K번째 수

 

자바 API의 sort 알고리즘과 Quick Selection을 배울 수 있는 문제.

 

문제링크

11004번: K번째 수 (acmicpc.net)

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

BJ_S5_11004_K번째 수 (naver.com)

BJ_S5_11004_K번째 수

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package algo_class;

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

/**
 * @author 은서파
 * @since 2021. 8. 16.
 * @see
 * @perf
 * @category #
 * @고려사항
 * @입력사항
 * @출력사항
 */

public class BJ_S5_11004_K번째수 {

	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;

	static int N, K;

	public static void main(String[] args) throws IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		K = Integer.parseInt(tokens.nextToken()) - 1; // K번째를 index로 변경하기 위해서...

		tokens = new StringTokenizer(input.readLine());
		//byPrimitiveArray(tokens);
		//byObjectArray(tokens);
		int[] nums = new int[N];
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.valueOf(tokens.nextToken());
		}
		quickSelection(nums, 0, N - 1);
		//System.out.println(Arrays.toString(nums));
		System.out.println(nums[K]);
	}
	// 501752	1192
	private static void quickSelection(int[] nums, int left, int right) {
		if (left >= right) {
			return;
		}

		int pivotIdx = partition(nums, left, right);
		if (K < pivotIdx) {
			quickSelection(nums, left, pivotIdx - 1);
		} else if (K > pivotIdx) {
			quickSelection(nums, pivotIdx + 1, right);
		} else {
			return;
		}

	}

	// Quick Sort -->Pivot의 위치 결정 후 pivot 보다 큰 녀석, 작은 녀석들로 분
	// pivot의 위치는 : 맨 처음, 맨 마지막, 중간. 이 문제는 중간값을 이용한 pivot 필요 
	// pivot의 초기 위치를 왼쪽에 놓고 시작해야 pass
	private static int partition(int[] nums, int left, int right) {
		// 1. pivot의 값과 위치를 결정하자.
		int mid = (left + right) / 2;
		swap(nums, mid, left);//pivot 값이 왼쪽으로 이동

		int pv = nums[left];
		int pi = left;

		while (left < right) {
			// 뒤에서 부터 pv보다 작거나 같은녀석의 위치를 찾자.
			while (nums[right] > pv && left < right) {
				right--;
			}
			// 앞에서 부터 pv 보다 큰 녀석의 위치를 찾자.
			while (nums[left] <= pv && left < right) {
				left++;
			}
			swap(nums, left, right);
		}
		swap(nums, left, pi);
		return left; //pivot의 index
	}

	private static void swap(int[] nums, int a, int b) {
		int temp = nums[a];
		nums[a] = nums[b];
		nums[b] = temp;
	}

	// 객체형 배열 - Merge Sort 활용: 579092	4684 
	private static void byObjectArray(StringTokenizer tokens) {
		Integer[] nums = new Integer[N];
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.valueOf(tokens.nextToken());
		}
		Arrays.sort(nums);
		System.out.println(nums[K]);
	}

	// 기본형 배열 - Quick Sort 활용  - 92% 시간초과: 아마도 이미 정렬된 큰 데이터 테케가 있을 것이다.
	private static void byPrimitiveArray(StringTokenizer tokens) {
		int[] nums = new int[N];
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(tokens.nextToken());
		}
		Arrays.sort(nums);
		System.out.println(nums[K]);
	}

	private static String src = "5 2\n"
								+ "4 1 2 3 5";

}