< 프로그래머스 C++ > K번째 수

---

문제 해석

자르기 > 정렬 > 특정 위치 원소 추출 세 단계를 반복하면 되기 때문에 간단한 문제이다.

 

하지만 인덱스의 위치와 문제에서 원하는 순서의 숫자를 헷갈리기 쉽다. 이 부분을 주의하며 풀어야 한다.

---

문제 풀이

#include <string>
#include <vector>
#include <algorithm>
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> sliced(
            array.begin() + commands[i][0] - 1,
            array.begin() + commands[i][1]
        );
        
        sort(sliced.begin(), sliced.end());
        
        answer.push_back(sliced[commands[i][2] - 1]);
    }
    return answer;
}

 

풀이 흐름

vector 범위 생성자로 구간 복사 -> sort로 정렬 -> k-1번째 원소를 answer에 추가 후 리턴

 

핵심 포인트

vector 범위 생성자

vector 범위 생성자에서 iterator 두 개를 넘기면 (first, last) 구간을 복사한 새 vector가 만들어지는데, 문제에서 원하는 범위를 추출하기 위해서는 sliced의 첫번째 인자에는 first -1을, 두번째는 그냥 last를 입력하는 것이다.

vector<int> v = {10, 20, 30, 40, 50};
vector<int> sliced(v.begin() + 1, v.begin() + 4);
// sliced = {20, 30, 40}   ← 인덱스 4는 포함 안 됨!

sliced의 자르기 방식은 다음과 같다.

따라서 마지막에는 -1을 붙여주지 않아야 문제에서 원하는 범위가 추출된다.

 

---

트러블 슈터

1. 결과가 하나씩 모자람

문제 : [5, 2, 6, 3] 이어야 할 sliced가 [5, 2, 6]만 출력됨

 

원인 : 끝 인덱스에도 -1을 해서 sliced함

그래서 추출된 인덱스가 하나씩 모자람

 

해결 : iterator의 끝은 포함이 되지 않는 다는 것을 알게 되어 -1을 제거하고 sliced함

array.begin() + commands[i][1] - 1
>> array.begin() + commands[i][1]

 

2. K번째에서 엉뚱한 값이 나옴

문제 : 정렬된 [2, 3, 5, 6]에서 3번째를 5대신 6으로 반환.

 

원인 : sliced[commands[i][2]]로 사용해서 k = 3일 때, 5 대신 6으로 출력되는 것이었다.

 

해결 : k의 숫자도 인덱스의 시작 위치를 감안하여 -1을 추가해주면 해결 된다.

sliced[commands[i][2]]
>> sliced[commands[i][2] - 1]