[JAVA] 백준 25305_커트라인

 

[문제링크]

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

 

📌 문제 탐색하기

N명의 학생중에서 가장 점수가 높은 K명의 학생의 점수 커트라인을 구하는 문제이다. 

커트라인은 상을 받은 학생중에서 가장 점수가 낮은 학생의 점수값을 출력하면 되는 문제이기때문에 입력받은 점수를 내림차순으로 정렬하고 그중에 k번째 점수를 출력하면 되는 문제이다. 

📌 가능한 시간복잡도

1. 입력한 점수를 정렬해야한다. O(n logn)

2. k번째 값을 출력한다. O(1)

 

따라서, 가능한 시간복잡도는 O(N logN) 입니다.

📌 코드 설계하기

학생수 N과 상받을 학생수 K명의 값을 입력받고 -> 입력받은 학생수 N명의 점수를 정렬하고 -> 정렬된 값에서 k번째 값을 출력한다.

 

이 순서대로 코드를 설계함. 

하지만, 오름차순 Array.sort( ) 사용만 계속 진행해서 내림차순에 대해서 기억이 나지 않음 이슈로 인해서 

오름차순으로 입력받은 후에 거꾸로 뒤에서부터 k번째를 출력하는 방식으로 변경해서 코드 설계 진행함. 

 

📌 정답 코드

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt();
        int k = in.nextInt();

        int[] scores = new int[N];

        for (int i = 0; i < N; i++) {
            scores[i] = in.nextInt(); 
        }

        Arrays.sort(scores);
        int cutline = scores[N - k];

        System.out.println(cutline);
    }
}

📌 실수 정리

1회차 : 내림차순으로 정렬을 활용해서 문제를 풀고 싶었는데 오름차순 정렬 방식만 기억이 나서 오름차순 정렬을 해서 처음 생각한 방식의 반대로 뒤에서부터 k번째 점수를 찾아서 출력하는 방식을 사용함.

=> 내림차순 정렬을 처리하는 방법 한번 더 공부하는 계기가 되었음.

    - 내림차순 정렬 방식 : Arrays.sort(scores, Collections.reverseOrder()) 를 사용하면 내림차순 정렬처리가 완료된다. 

 

2회차 : 그냥 구글링한대로 Collections.reverseOrder() 을 냅다 사용하니까 컴파일에러...

=> Collections.reverseOrder()  는 int[] 타임으로 선언하는게 아니라 integer[] 타입에서만 적용이 가능하다.

 

3회차 : 수정했는데도 컴파일에러 해결이 안됨... 다시 구글링 진행 결과 위에 import 하지 않아서...;;;

import java.util.Collections; 추가하니까 내가 원하던대로 내림차순을 활용한 문제풀이 가능...!! 

 

📌 알게된 다른 코드( 내림차순 활용 ) 

import java.util.Scanner;
import java.util.Arrays;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt(); 
        int k = in.nextInt(); 

        Integer[] scores = new Integer[N];

        for (int i = 0; i < N; i++) {
            scores[i] = in.nextInt(); 
        }

        Arrays.sort(scores, Collections.reverseOrder());

        int cutline = scores[k - 1];

        System.out.println(cutline);
    }
}