[JAVA] 백준 25305번 - 커트라인

https://www.acmicpc.net/problem/25305

25305번: 커트라인

 

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] arr = new int[10001];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[Integer.parseInt(st.nextToken())]++;
        }

        for(int i=10000; i>=0; i--){ // 높은 순서대로 카운팅해야 하므로 거꾸로 탐색
            while(arr[i]>0){
                arr[i]--;
                k--;

                if(k==0){
                    System.out.println(i);
                    break;
                }
            }
        }
    }
}

 

 

바로 이전 정렬 문제에서 카운팅 정렬을 사용했기 때문에 복습겸 이 문제도 카운팅 정렬으로 풀어봤다.

입력받은 값의 인덱스에 입력받은 수의 빈도수를 저장하고,

배열의 역방향으로 탐색하면서 빈도수와 k를 감소시켜 k가 0이 되었을때의 배열 인덱스를 출력한다.