[정렬/C++] K번째수

문제

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구한다.

​

입출력 예시

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.

[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.

[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

​

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(int a, int b){
    return a < b;
}

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    int start, end, k = 0;
    for(int i=0; i<commands.size(); i++){
        vector<int> temp;  // 자른 배열을 저장하는 변수
        start = commands[i][0] - 1;
        end = commands[i][1] - 1;
        k = commands[i][2] - 1;
        temp.resize(end-start+1);
        // 배열을 잘라서 temp에 복사
        copy(array.begin() + start, array.begin()+end+1, temp.begin());
    
        if(start == end){
            answer.push_back(array[start]);
        }
        else{ // 정렬 후 answer 배열에 k번째 요소 추가
            sort(temp.begin(), temp.end());
            answer.push_back(temp[k]);
        }
    }
    
    return answer;
}

 

 

 

문제 출처: 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/42748?language=cpp