[프로그래머스/C++] ㅡ LV1 - K번째수

문제

programmers.co.kr/learn/courses/30/lessons/42748

코딩테스트 연습 - K번째수

풀이

#include <algorithm>
#include <vector>

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    for (int i=0; i<commands.size(); i++) {
        vector<int> middle;
        for (int j=commands[i][0]-1; j<=commands[i][1]-1; j++) {	// 새로운 배열 값 할당
            middle.push_back(array[j]);
        }
        sort(middle.begin(), middle.end());		// 새 배열 정렬
        answer.push_back(middle[commands[i][2]-1]);		// answer 배열로 k번째 값 옮김
    }
    return answer;
}

개념

C++ STL 중 sort 의 문법적인 부분이 은근 헷갈린다.

vector로 정의된 배열은 간단하다.

v.begin(), v.end()를 sort에 인자로 넣으면 된다.

 

하지만 일반적인 배열의 경우, sort (a, b)에 넣어야되는 a, b를 실수하기 쉽다.

a : 배열의 포인터 ( 주소를 적으면 된다! ex. arr[] 배열의 경우 arr )

b : 배열의 포인터 + 크기 (ex. arr + 10 )

---

풀이

arrary를 i~j까지 자르고, 정렬한 뒤 k번째를 고르면 된다.

그러한 test case가 commands의 행이다.

따라서 다음 기능을 commands.size() 만큼 반복한다.

 

middle 배열을 만든다. 

그리고 주어진 i~j를 for문의 반복 범위로 하여 그 때마다 해당 배열값을 middle에 대입한다.

그리고 middle을 vector 문법을 사용해 손쉽게 sort한다.

middle에서 k번째 수를 참조해서 answer에 대입하면 된다!

 

---

+a

 

번거로운 부분은 배열이 0부터 시작된다는 것이다.

주어지는 값은 1부터 시작되는 '번째' 개념이므로 계속 -1을 해주어야 한다.

 

 

다른풀이(실패..)

#include <algorithm>
#include <vector>

using namespace std;

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

아예 새로운 배열을 만들지 않고, 기존 배열안에서 처리하는 방법을 생각했다.

이 경우 코드는 훨씬 간단해지는데 가시성은 좀 떨어지는 것 같다.

 

이렇게 작성하면 간과되는 부분이 있는 것 같다..

answer = array 해서 확인한 결과 sort 과정까지는 문제가 없다.

answer.push_back(array[commands[i][0]+commands[i][2]-2]);

이 값이 문제인 것 같은데 좀 더 고민해봐야겠다..