[백준] 커트라인 25305번

문제 힌트

1. 입력 데이터 처리:
   • 첫 번째 입력 줄은 공백으로 구분된 두 개의 정수 n과 cutLine을 포함합니다. n은 점수의 개수, cutLine은 컷라인 순위를 나타냅니다.
   • 두 번째 입력 줄은 공백으로 구분된 n개의 정수 점수를 포함합니다.
2. 정렬:
   • 점수를 내림차순으로 정렬합니다. 이를 위해 삽입 정렬(insertion sort) 알고리즘을 사용합니다. 내림차순 정렬을 위해서는 정렬 조건을 변경해야 합니다.
3. 컷라인 점수 출력:
   • 정렬된 점수 배열에서 cutLine에 해당하는 점수를 출력합니다. 컷라인 순위는 1-based 인덱스를 사용하므로, 배열의 인덱스는 cutLine-1이 됩니다.
4. 정렬 알고리즘:
   • Arrays.sort()를 사용하셔서 for문을 돌리셔도 됩니다.
   • 저는 삽입 정렬을 사용햇습니다
   • 배열의 첫 번째 요소는 이미 정렬되어 있다고 가정합니다.
   • 두 번째 요소부터 마지막 요소까지 순회하면서, 현재 요소를 올바른 위치에 삽입합니다.
   • 정렬 조건은 현재 요소가 이전 요소보다 큰 경우(내림차순 정렬)입니다.

 

정답은 더보기 클릭

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        // 첫 번째 입력 라인에서 n과 cutLine 값을 받아옴
        String[] input = in.nextLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int cutLine = Integer.parseInt(input[1]);
        
        // 두 번째 입력 라인에서 점수 배열을 받아옴
        String[] strArr = in.nextLine().split(" ");
        int[] scores = new int[n];
        
        // 점수 배열을 정수형 배열로 변환
        for (int i = 0; i < n; i++) {
            scores[i] = Integer.parseInt(strArr[i]);
        }
        
        // 삽입 정렬을 사용하여 배열 정렬
        insertionSort(scores);
        
        // 컷라인에 해당하는 점수를 출력 (0-based 인덱스를 사용하므로 cutLine-1)
        System.out.println(scores[cutLine - 1]);
    }

    // 삽입 정렬 메서드
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int target = arr[i];
            int j = i - 1;
            
            // 정렬된 부분에서 타겟이 들어갈 위치를 찾음 (내림차순 정렬)
            while (j >= 0 && arr[j] < target) {
                arr[j + 1] = arr[j];
                j--;
            }
            
            arr[j + 1] = target;
        }
    }
}