[백준] 25305번 - 커트라인

문제 링크 : https://www.acmicpc.net/problem/25305

문제 탐색하기

1) 문제 분석

N명의 학생이 입력된다.
점수가 가장 높은 k명의 점수 중 가장 낮은 사람의 점수를 출력한다.

2) 가능한 시간복잡도

(1) 입력 처리

첫 줄(N, K)과 점수 한 줄을 split()으로 처리 → O(1)
점수 N개를 split → map(Number)로 숫자 배열로 변환 → O(N)

(2) 정렬 처리

점수 배열을 내림차순 정렬 → O(N log N)

(3) 커트라인 추출

k번째 점수 접근 → O(1)

(4) 전체 시간복잡도

O(N) + O(N log N) + O(1) = O(N log N)

3) 알고리즘 선택 이유

이 문제는 상위 K명에게 상을 수여할 때, 커트라인(가장 낮은 수상 점수)을 구하는 문제이다.
따라서 전체 점수를 내림차순으로 정렬한 뒤, k번째 점수(index = k - 1)를 출력하는 것이 직관적이고 정확한 방식이라고 생각했다.
점수 배열의 길이(N)가 매우 크지 않다면 정렬 후 접근 방식이 가장 명확하고 구현이 쉬울 것 같았다.
정렬 연산은 O(N log N)으로 비교적 효율적이며, 커트라인 추출은 O(1)로 즉시 가능할듯 하다.-> 즉, 정렬 기반의 접근법은 시간복잡도 측면에서도 효율적이며, 문제의 요구 조건을 단순하게 해결할 수 있는 최적의 선택이다.

코드 설계하기

1. 실행 구조

1) 총 학생 수, 상을 받는 인원, N명의 점수를 입력받는다.

2) 커트라인의 인원을 구한다.

3) 두 번째 줄의 점수들을 공백 기준으로 분리하고, 숫자로 변환하여 배열로 저장한다.

4) 정렬된 배열에서 K번째 점수(index = K-1)를 커트라인으로 설정한다.

5) 결과값을 출력한다.

2. 고민이 되었던 부분

JavaScript

// 기존 코드
// 첫 번째 줄에서 응시자 수 N과 상을 받는 사람 수 k를 분리하여 추출
const cutline = Number(input[0].trim().split(" ")[1]); // k 값만 사용

// 두 번째 줄에서 점수들을 공백 기준으로 나눈 뒤, 숫자 배열로 변환 후 내림차순 정렬
const numbers = input[1].trim().split(" ").map(Number).sort((a, b) => b - a);



// 수정 코드
function getCutlineScore(input) {
  const [N, k] = input[0].split(' ').map(Number);
  const scores = input[1].split(' ').map(Number);

  if (k > N) {
    throw new Error("k는 N보다 클 수 없습니다.");
  }

  scores.sort((a, b) => b - a);
  return scores[k - 1];
}

처음에는 문제 풀이를 단순하게 입력 → 정렬 → 출력의 절차적 흐름으로 구성했다. 이처럼 한 파일 안에서 순서대로 실행하는 방식이 가장 빠르고 간단하게 보였기 때문에, 굳이 함수로 분리할 필요가 있을까 고민이 되었다.

그러나 점차 로직을 분리하면서 코드의 재사용성과 가독성, 그리고 테스트 가능성이 중요하다는 점을 떠올리게 되었다. 특히 실제 개발 환경이나 팀 프로젝트에서는 기능을 모듈화하고, 각 함수의 역할을 명확히 나누는 것이 유지보수에 유리하다는 점을 알고 있었기 때문에, 이번 기회에 함수화를 적용해보았다.

그 결과 입력 파싱과 핵심 로직을 나누어 구성할 수 있었고, 나중에 동일한 로직을 다른 입력값으로 테스트할 때도 훨씬 수월하다는 점을 직접 체감할 수 있었다. 함수화는 단지 "형식적인 분리"가 아니라, 문제 해결 흐름을 더 명확하게 구조화할 수 있는 개발 습관이라는 걸 깨닫는 계기가 되었다.

정답 코드

JavaScript

// 사용 언어 : Javascript

// 기존 코드
// const fs = require('fs');

// // 입력을 한 줄씩 받아와 문자열 배열로 변환
// const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// // 첫 번째 줄에서 응시자 수 N과 상을 받는 사람 수 k를 분리하여 추출
// const cutline = Number(input[0].trim().split(" ")[1]); // k 값만 사용

// // 두 번째 줄에서 점수들을 공백 기준으로 나눈 뒤, 숫자 배열로 변환 후 내림차순 정렬
// const numbers = input[1].trim().split(" ").map(Number).sort((a, b) => b - a);

// // 커트라인 점수(상위 k명 중 가장 낮은 점수)를 출력
// console.log(numbers[cutline - 1]);


// 수정 코드
function getCutlineScore(input) {
    const [N, k] = input[0].split(' ').map(Number);
    const scores = input[1].split(' ').map(Number);

    if (k > N) {
        throw new Error("k는 N보다 클 수 없습니다.");
    }

    scores.sort((a, b) => b - a);
    return scores[k - 1];
}

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
console.log(getCutlineScore(input));

마무리하며

정렬 문제도 충분히 흥미로웠지만, 오늘 풀었던 구현/시뮬레이션 문제는 또 다른 재미가 있었다. 이 유형은 어떻게 푸는지를 넘어, 실제로 조건을 코드로 옮겨 정확하게 구현해낼 수 있는지를 고민하게 만들어주었다. 특히 현실 세계의 동작을 코드로 하나씩 따라가며, 상태, 시간 흐름, 위치 이동 등을 순차적으로 시뮬레이션해보는 과정이 매우 흥미로웠다.

또한 이번 문제를 풀면서 단순히 정답만 맞추는 것이 아니라, 코드의 가독성과 구조를 고려해 함수 형태로 리팩토링해본 것도 인상 깊었다. 앞으로 문제를 풀어나갈 때도 단순한 해결을 넘어서, 더 나은 로직 구성과 설계 방식에 대해서도 꾸준히 고민해보고 싶다.

최근 글