[프로그래머스 42748] K번째수

February 14, 2026

AlgorithmSort

출처: 프로그래머스 42748
분류: 정렬 · Lv.1

문제

배열 array와 명령 [i, j, k]가 여러 개 주어진다. 각 명령마다 array의 i번째부터 j번째까지 잘라 정렬한 뒤 k번째 수를 반환한다. 인덱스는 1-based다.

핵심

명령마다 부분 배열 복사 → 정렬 → k번째 접근. 그대로 구현하면 된다.

풀이

#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    for (const auto& cmd : commands) {
        vector<int> sub(array.begin() + cmd[0] - 1, array.begin() + cmd[1]);
        sort(sub.begin(), sub.end());
        answer.push_back(sub[cmd[2] - 1]);
    }
    return answer;
}

메모

vector<int> sub(begin, end) 범위 생성자로 부분 배열을 복사한다. cmd[0] - 1은 1-based → 0-based 변환, cmd[1]은 변환하지 않는다 (범위 끝은 exclusive이므로 j번째까지 포함)
nth_element(sub.begin(), sub.begin() + cmd[2] - 1, sub.end())를 쓰면 전체 정렬 없이 k번째 원소만 O(N)에 구할 수 있다. 이 문제는 배열이 작아서 차이가 없다

복잡도

풀이	시간	공간
부분 정렬	O(M · N log N)	O(N)
nth_element	O(M · N)	O(N)

M = commands 수, N = 부분 배열 최대 길이