프로그래머스 lv 1. 42748 c++ K번째수

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

 

#include <bits/stdc++.h>

using namespace std;

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

 

++++++++++

다른 사람의 풀이를 보니까, 위의 내가 작성한 풀이는 vector 부분으로 떼어와서 만드는데, 전체를 temp 벡터로 복사해서 그걸 일부분만 sort하는 풀이가 있어서 첨부해보겠다. 

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

    return answer;
}

이렇게 작성하는것이 아무래도 내가 위에 작성할때 일부분만 vector에다가 넣는 코드가 없어서 조금 더 간결해보이는 경향이 있는것 같다

하지만 시간복잡도 면에서는 결국 벡터를 sort() 를 이용해서 정렬하고 그걸 반복문으로 돌리는 것이라 동일할것이다. 

하지만 오히려 어차피 메모리가 엄청나게 타이트하지 않다면 위와 같이 코드를 작성하는것이 더욱 바람직한 알고리즘 문제해결 전략이라고 생각된다.