25305. 커트라인 (자바, Java)

counting 정렬을 미리 만들어놓고, 그걸 복붙하여 개량해서 풀었습니다.

 

counting 정렬 관련은 다음 글을 참고하세요.

https://mewtwo.tistory.com/121

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str1 = br.readLine();
		String str2 = br.readLine();
		String[] arr1 = str1.split(" ");
		String[] arr2 = str2.split(" ");
		int n = Integer.parseInt(arr1[0]);
		int k = Integer.parseInt(arr1[1]);
		int[] x = new int[n];
		
		for (int i=0; i<n; i++) {
			x[i] = Integer.parseInt(arr2[i]);			
		}
		
		int max = 0;
		
		for (int i=0; i<n; i++) {
			if (x[i]>max) {
				max = x[i];				
			}
		}
		
		System.out.println(count(x,max)[x.length-k]);

	}
	
	public static int[] count(int[] arr, int max) {
		
		int[] result = new int[arr.length];
		int[] ct = new int[max+1];
		
		for (int i=0; i<=max; i++) {
			
			for (int j=0; j<arr.length; j++) {				
				if (arr[j] == i) {
					ct[i]++;					
				}				
			}			
		}
		
		for (int i=1; i<=max; i++) {
			
			ct[i] += ct[i-1];
			
		}		
		
		for (int i=result.length-1; i>=0; i--) {
			int value = arr[i];
			ct[value]--;
			result[ct[value]] = value;
			
		}
		
		return result;
		
	}

}