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

코딩테스트 고득점 kit 정렬파트 1번 K번째 수

 

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/42748

프로그래머스

 

[해결법]

벡터에서 i~j 숫자를 추출하고 오름차순 정렬한 후, k번째 수를 뽑는 문제이다.

순서대로 차근차근 하니까 금방 풀렸다.

but 백만년만에 C++ 다시 잡으니 함수가 헷갈린다... 감잡자 keep going...

 

[알아둘 것]

1. 벡터 부분추출

vector<int> partArray(array.begin() + beginIndex, array.begin() + endIndex);

2. 벡터 정렬

sort(v.begin(), v.end()); // 벡터 전체를 오름차순으로 정렬할 때
sort(v.begin(), v.end(), greater<int>()); // 벡터 전체를 내림차순으로 정렬할 때

 

[코드]

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

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    
    //명령 갯수만큼 반복
    for(int i = 0; i < commands.size(); i++){
        
        //명령어 값 보기좋게 선언
        int beginIndex = commands[i][0];
        int endIndex = commands[i][1];
        int answerIndex = commands[i][2];
        
        //beginInde ~ endIndex까지 값 추출
        vector<int> partArray(array.begin() + beginIndex - 1, array.begin() + endIndex);

        //오름차순 정렬
        sort(partArray.begin(), partArray.end());

        //K번째 수 추출
        answer.push_back(partArray[answerIndex - 1]);
    }
    
    return answer;
}

시간복잡도: for반복문 O(N) x 벡터 오름차순 정렬 Quick 정렬 O(NlogN) = O(N^2logN)