[코딩테스트 챌린지] 백준 25305 커트라인 (java)

문제

 

 

문제 탐색하기

1. 주어진 점수 배열 정렬하기

N명의 학생중 k명의 학생들이 상을 받을 수 있는데 여기서 상을 받는 커트라인을 구하는 문제입니다.

즉, N명의 학생 중 k번째로 점수가 높은 학생의 점수를 출력하면 되는 문제입니다.

주어지는 점수를 배열로 저장한 뒤에 오름차순 혹은 내림차순으로 정렬한 뒤 원하는 인덱스로 뽑으면 되는 간단한 문제입니다.

 

Arrays sort()를 활용하면 참조형 배열일 경우에는 최악의 경우에도 시간복잡도는 O(nlog(n)) 입니다.

주어진 배열을 참조형 배열인 Integer 배열로 저장해서 정렬하고 N의 최대값은 1000이므로 충분히 시간내에 답을 낼 수 있는 문제입니다.

 

여기서 딱 커트라인에 걸리는 사람의 점수를 출력하기 위해서는 배열을 내림차순으로 정렬해서 K-1 번째 인덱스의 점수를 구하는 것과

오름차순으로 정렬해서 N-k 번째 인덱스의 점수를 구하면 될 것입니다.

 

 

코드 설계하기

1. 응시자 수를 변수에 저장
2. 상을 받는 사람 수를 변수에 저장
3. 점수를 Integer 배열에 저장
4. 배열을 정렬
   1. 오름차순으로 정렬할 경우, 배열의 마지막에서 k번째를 출력 (인덱스 : N-k)
   2. 내림차순으로 정렬할 경우,  배열에서 k번째 점수를 출력 (인덱스 : k-1)

 

시도 회차 수정 사항

1회차) Arrays.sort() 를 통해 내림차순으로 정렬하려 할때 기존에는 int[] 배열을 정렬하려고 했습니다. 하지만 내림차순으로 정렬할 경우 참조형 배열만 매개변수로 넣을 수 있다는 것을 알게되었고 Integer[] 배열을 넣어서 내림차순으로 정렬할 수 있었습니다. 이 과정을 통해 Arrays.sort() 는 시간복잡도가 최악의 경우 O(n^2)로 정렬하는 것으로 알고있었는데 참조형 배열은 최악의 경우라도 시간복잡도가 O(nlog(n)) 인 것을 알 수 있게되는 좋은 기회였습니다.

 

정답 코드

1. 내림차순 정렬

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

public class Cutline {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(st.nextToken()); // 1. 응시자 수
        int k = Integer.parseInt(st.nextToken()); // 2. 상을 받는 사람 수

        st = new StringTokenizer(reader.readLine());
        Integer[] scores = new Integer[N];
        for(int i=0; i<N; i++){
            // 3. 점수를 Integer 배열에 저장
            scores[i] = Integer.parseInt(st.nextToken());
        }

        // 4. 배열을 내림차순으로 정렬
        Arrays.sort(scores, Collections.reverseOrder());

        // 5. 커트라인 점수인 배열에서 k번째 점수를 출력 --> 인덱스 : k-1
        System.out.println(scores[k-1]);
    }
}

 

2. 오름차순 정렬

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

public class Cutline {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(st.nextToken()); // 1. 응시자 수
        int k = Integer.parseInt(st.nextToken()); // 2. 상을 받는 사람 수

        st = new StringTokenizer(reader.readLine());
        Integer[] scores = new Integer[N];
        for(int i=0; i<N; i++){
            // 3. 점수를 Integer 배열에 저장
            scores[i] = Integer.parseInt(st.nextToken());
        }

        // 4. 배열을 오름차순으로 정렬
        Arrays.sort(scores);

        // 5. 오름차순으로 정렬했기에 배열의 마지막에서 k번째를 출력 --> 인덱스 : N-k
        System.out.println(scores[N-k]);
    }
}