[Java] 백준(브론즈-2) 25305번 - 커트라인

입출력 예시

Input

5 2
100 76 85 93 98

Output

98

문제 풀이

---

문제의 요구사항을 잘 보면 주어진 점수들을 내림차순으로 정렬한 후 k번째 점수를 구해야 한다.
여기서 주어진 점수들을 내림차순으로 정렬하는 것이 핵심이다.
내림차순으로 정렬하는 다양한 방식 중에서 int 배열을 이용한 방식과 Integer 배열을 이용한 방식 두가지로 풀어보았다.

int 배열 활용 - 오름차순 정렬 후 역순으로 접근하기

기본 타입 배열인 int 배열을 가지고 역순으로 정렬할 수는 없기 때문에, 역순으로 접근하거나, -1을 곱해서 재 정렬하는 등으로 진행해야 한다.
이 문제에서는 오름차순 정렬된 배열을 가지고 역순으로 다시 저장하는 방식으로 진행해보려 한다.

코드를 작성해보자.

int[] score = new int[N];
int[] desc_score = new int[N];

for(int i=0; i<score.length; i++) {
    score[i] = Integer.parseInt(st.nextToken());
}

먼저 주어진 점수를 입력받아 오름차순으로 정렬할 score 배열과 역순으로 새로 저장할 desc_score 배열을 생성하자.
그리고 입력 점수를 score 배열에 공백기준으로 저장한다.

Arrays.sort(score);
for(int i=0; i<desc_score.length; i++) {
    desc_score[i] = score[score.length-i-1];
}   

입력점수를 그대로 저장한 score 배열을 오름차순으루 정렬한 뒤, 순회하면서 마지막 원소부터 역순으로 desc_score에 저장하면 내림차순으로 졍렬된다.

bw.write(desc_score[k-1]+"\n");

오름차순 정렬된 배열에서 k번째 수를 출력하면 커트라인이 몇 점인지 구할 수 있다.

Integer 배열 활용 - Collections.reverseOrder()

배열을 내림차순으로 정렬할 때는 Collections 클래스의 reverseOrder() 함수를 사용하면 된다.
사실 Collections.reverseOrder()는 Comparator 객체이기 때문에 직접 구현해야하지만 기본 타입의 int 배열을 래퍼 클래스인 Integer 배열로 만들어 Comparator를 두번째 인자에 넣어주면 역순으로 정렬된다.

Integer 배열을 이용해 코드를 작성해보자.

Integer[] desc_score = Arrays.stream(score).boxed().toArray(Integer[]::new); 
Arrays.sort(desc_arr, Collections.reverseOrder());

내림차순으로 저장할 desc_score 객체 배열은 기본 타입의 배열을 객체 스트림형태로 변환한 후 배열의 형태로 변환한다.
그러면 sort() 함수의 두번째 인자로 Collections.reverseOrder()를 전달할 수 있다.

위 내림차순 정렬 방식에 대한 자세한 내용은 이전에 풀었던 최솟값 만들기 게시글에서 참고할 수 있다.

작성코드

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

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

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

        st = new StringTokenizer(br.readLine());
        int[] score = new int[N];
        int[] desc_score = new int[N];
        // Integer[] desc_score = new Integer[N];

        for(int i=0; i<score.length; i++) {
            score[i] = Integer.parseInt(st.nextToken());
        }

        desc_score = descending1(score);
        // desc_score = descending2(score);
        
        bw.write(desc_score[k-1]+"\n");

        bw.flush();
        bw.close();
        br.close();
    }

    public static int[] descending1(int[] arr) {
        int[] desc_arr = new int[arr.length];
        Arrays.sort(arr);
        for(int i=0; i<desc_arr.length; i++) {
            desc_arr[i] = arr[arr.length-i-1];
        }   
        return desc_arr;
    }

    public static Integer[] descending2(int[] arr) {
        Integer[] desc_arr = Arrays.stream(arr).boxed().toArray(Integer[]::new); 
        Arrays.sort(desc_arr, Collections.reverseOrder());
        return desc_arr;
    }
}

회고

• 아직까지는 Integer 등 래퍼클래스를 이용한 정렬방식보다는 int 등의 기본배열을 활용하는 것이 더 익숙하지만, 상황에 따라 다양한 내림차순 방법을 잘 활용해야겠다.