Lv1_[K번째수, C++] 풀이 및 알고리즘 정리 - 프로그래머스

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

알고리즘

1. 정렬해야하는 부분을 찾아서 잘라내기
2. 잘라낸 부분을 정렬

인자값으로 주어지기 때문에 주어진 인덱스와 배열의 인덱스를 맞춰서 잘 설정해주면 됨
(0과 1 서로 시작점이 다르기 때문)

 

• start = item[0] - 1;       (i번째 숫자)
• end = item[1];             (j번째 숫자)
• k_index = item[2] - 1; (k번째 숫자)

 

배열을 잘라내기 위해서 copy i번째 숫자부터 j번째 숫자이면 [i-1, j) 가 됨

copy로 배열을 잘라났으면 sort로 오름차순 정렬 후 k번째 숫자를 출력하면 풀이는 끝

코드화 시키면 다음과 같다.

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<int> solution(vector<int> array, vector<vector<int> > commands)
{
    vector<int> answer;
 
    for (auto item : commands)
    {
        int start = item[0] - 1;
        int end = item[1];
        int k_index = item[2] - 1;
 
        vector<int> tmp_vec;
        std::copy(array.begin()+start, array.begin()+end, back_inserter(tmp_vec));
        std::sort(tmp_vec.begin(), tmp_vec.end());
 
        answer.push_back(tmp_vec[k_index]);
    }
 
    return answer;
}

 

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓