[BOJ 25305] 커트라인 - [구현 / 정렬]

[BOJ 25305] 커트라인 - [구현 / 정렬]

문제 링크

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

문제 요약

$N$명의 학생이 시험을 보았을 때, 점수가 가장 높은 $k$명에게 상을 준다. 이때 상을 받는 사람 중 가장 낮은 점수(커트라인)를 구하는 문제이다.

접근 방법

• 자료구조: std::vector<int> (점수들을 저장하고 정렬하기 위해 사용)
• 알고리즘: 정렬 (Sorting)
• 핵심 아이디어: 모든 점수를 입력받아 내림차순(큰 순서대로)으로 정렬한 뒤, $k$번째 위치한 값을 찾는다.

풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 입출력 성능 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, k;
    // N: 응시자 수, k: 상을 받는 사람의 수
    if (!(cin >> N >> k)) return 0;

    vector<int> scores(N);
    for (int i = 0; i < N; i++) {
        cin >> scores[i];
    }

    // 내림차순 정렬 (점수가 높은 순서대로)
    sort(scores.begin(), scores.end(), greater<int>());

    // k번째 사람의 점수 출력 (인덱스는 0부터 시작하므로 k-1)
    cout << scores[k - 1] << "\n";

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O(N \log N)$ (정렬 알고리즘 std::sort의 시간 복잡도)
• 공간 복잡도: $O(N)$ (학생들의 점수를 저장하기 위한 벡터 공간)

실행 결과 (예상)

• 메모리: 약 2024 KB
• 시간: 0 ms

핵심 포인트

1. 정렬 방향: 문제에서 '높은 점수' 기준이므로 내림차순 정렬을 하거나, 오름차순 정렬 후 뒤에서 $k$번째를 찾아야 한다.
2. 인덱스 주의: 프로그래밍 언어의 배열 인덱스는 0부터 시작하므로, 문제의 $k$번째는 코드 상에서 k-1 인덱스임을 유의해야 한다.

예제 확인

• 예제 1:
  • 입력: 5 2 / 100 76 85 93 98
  • 정렬 후: 100 98 93 85 76
  • 2번째(index 1) 값: 98 (출력 일치)