프로그래머스) K번째 수

K번째 수

 

 

문제 설명

 

 

 

 

 

 

풀이

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

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    
    
    for(auto correct:commands)
    {
        vector<int>temp={};
        int _count=correct[0]-1;
        int _size=correct[1];
        int _select=correct[2]-1;
        for(int i=_count;i<_size;i++)
        {
            temp.push_back(array[i]);
        }
        ::sort(temp.begin(),temp.end());
        
        answer.push_back(temp[_select]);
        
    }    
    return answer;
}

 

처음으로 temp라는 벡터를 초기화시킨다. 이 temp는 루프를 돌 때 마다 초기화 되기 때문에 따로 초기화 시키지 않아도 된다. 다음으로 잘라낼 배열의 시작과 끝을 _count와 _size에 추출할 번호를 _select에 넣는다.

비어 있는 temp에 해당 배열을 잘라낸후 ::sort로 정렬한다. 그후 답안에 해당번째의 수를 넣는다.

시간복잡도는 for가 2번있으므로 O(n²)이된다.

 

 

 

 

 

(타인)모범답안

 

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

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++) 
    {
        int arr_count=commands[i][0] - 1;
        int arr_size=commands[i][1];
        int arr_select=commands[i][2]-1;
        temp = array;
        ::sort(temp.begin() + arr_count, temp.begin() + arr_size);
        answer.push_back(temp[arr_count+arr_select]);
    }

    return answer;
}

temp에 배열 자체를 넣고 해당 수에서 arr_count에서 arr_size까지 정렬하고 시작점 arr_count부터 arr_select번째의 수를 답안에 넣는다.

시간복잡도는 for1개로 O(n)이다.