[프로그래머스] K번째수 (C++)

문제 설명

배열이 하나 주어진다. 그 배열에서 i ~ j번째 수들만 따로 정렬한 뒤, k번째 수를 return해라. 이러한 일련의 과정은 반복되어야 한다. i, j, k에 대한 2차원 배열도 주어진다. 

 

입출력 예

array 배열이 { 1, 5, 2, 6, 3, 7, 4 }이고,

2차원 commands 배열이 { {2, 5, 3}, {4, 4, 1}, {1, 7, 3} }인 경우,

result 배열은 { 5, 6, 3 }이다.

 

풀이

정렬 문제이다. int 배열을 정렬하는 것이니 특정한 정렬 방식을 사용할 필요는 없어보여서 STL의 sort를 사용했다.

 

원본 배열인 answer를 보존하기 위해서 temp 배열을 하나 선언하고, 거기에 정렬할 값들을 넣는 식으로 구현했다.

 

1. temp배열에 주어진 범위 내의 array 배열의 원소를 넣는다.

 

2. sort()로 정렬한다.

 

3. k번째 수를 answer 배열에 추가한다.

 

코드

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

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands)
{
    vector<int> answer;
    vector<int> temp;
    for (int i = 0; i < commands.size(); i++)
    {
        temp.clear();
        for (int j = commands[i][0] - 1; j < commands[i][1]; j++)
        {
            temp.push_back(array[j]);
        }
        sort(temp.begin(), temp.end());
        answer.push_back(temp[commands[i][2] - 1]);
    }
    return answer;
}

int main(void)
{
    vector<int> array = { 1, 5, 2, 6, 3, 7, 4 };
    vector<vector<int>> commands = { {2, 5, 3}, {4, 4, 1}, {1, 7, 3} };
    vector<int> result;
    result = solution(array, commands);
    for (int i = 0; i < result.size(); i++)
    {
        cout << result[i] << endl;
    }
}