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

Python

def solution(array, commands):
    answer = []
    for com in commands:
	    answer.append(sorted(array[com[0]-1:com[1]])[com[2]-1])
    return answer

• 0부터 시작하므로 i와 j 모두 각각 주어진 수에서 인덱스로는 1 작은 값이고, 범위를 구할 때는 주어진 i에서 1 뺀 인덱스부터 j까지로 한다. 그럼 j는 포함되지 않으므로 구하려는 범위까지 구해진다.
• array를 자른 후 sorted로 정렬한다.

 

그럼 결과가 위와 같이 나오는데, 구하려는 수 k도 인덱스가 k-1이므로 1 작은 인덱스에서 수를 찾는다.

찾은 수를 answer에 넣는다.

 

---

C++

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

using namespace std;

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

• commands의 각 케이스마다 구해서 answer에 넣어야 하므로, 반복문으로 돌렸고, 최대한 이중 반복문이 안되도록 (그럼 O(n^2)으로 시간복잡도가 커지기 때문에) 문제를 해결하고자 했다.
• 그래서 반복문에서 commands의 각 배열로만 접근할 방법을 주고, 각 배열의 원소는 at()으로 구했다.  commands[i][0]로도 접근할 수 있다.
• 특정 범위의 vector를 가져올 sub는 vector(first, last)로 first에 array.begin()에서 어떤 원소부터 가져오는지, last에는 array.begin()에서부터 어떤 위치의 원소까지 가져오는지를 구했다. 이 부분에서도 copy도 써보고 몇번 오류가 있었는데 그냥 vector(first,last)로 초기화하면 됐다. (sub에 특정 범위로 잘라서 벡터로 넣기까지 시행착오가 좀 있었다.)
• 가져온 sub 벡터를 sort()를 이용해서 처음(sub.begin())부터 끝(sub.end())까지 정렬해줬다.
• 정렬 후, push_back으로 commands[i]의 세번째 원소, 즉 찾으려는 원소를 at으로 찾았다. 
• 반복문 마지막에는, 다시 sub를 사용하므로 clear()로 초기화해줬다.

 

 

Python, C++ 둘다 직접 구글링으로 함수 서치해가면서 결국 해결할 수 있어서 좋았다!😊