[프로그래머스 1 / c++] k번째 수

2차원 벡터를 인덱스로 접근해서 2차원 배열 처럼 푸는 문제이다

2차원 배열을 생각은 했으나, 벡터인데 인덱스를? 하고 헤맸던 문제이다

맞다. 벡터도 배열처럼 인덱스로 접근 가능하다. 찾아보며 벡터에 대해 좀 더 이해하게 됐던 문제이다

 

이렇게 for문을 2번써서 문제를 그대로 구현가능하지만

#include <bits/stdc++.h>

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    // 1번째 인덱스를 돌며 반복할 for문
    for(int i=0; i<commands.size(); i++){
    	// 재사용 해야하므로 array를 temp에 담아주고 반복마다 temp를 갱신하여 사용한다
        vector<int> temp;
        // 두번째 인덱스를 돌며 해당 범위의 array 값을 temp로 옮긴다
        for(int j=commands[i][0]-1; j<commands[i][1]; j++)
            temp.push_back(array[j]);
        // temp로 옮긴 값을 정렬한다
        sort(temp.begin(), temp.end());
        // commands의 3번째 인덱스값과 같은 temp의 값을 제출할 벡터에 올려준다
        answer.push_back(temp[commands[i][2]-1]);
    }
    return answer;
}

아래와 같이 commands의 각 인덱스를 변수로 정해서 보다 보기 좋게 구현하는 방법도 있고

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    for (auto proc : commands)
    {
        int start = proc[0];
        int end = proc[1];
        int num = proc[2];

        vector<int>temp(end - start + 1);
        for (int i = 0; i < end - start + 1;++i)
        {
            temp[i] = array[i + start-1];
        }
        sort(temp.begin(), temp.end());
        answer.push_back(temp[num-1]);

    }


    return answer;
}

아래와 같이  for문을 한번만 돌려서 속도를 향상시킬 수도 있다. 코딩테스트는 시간내에 풀어야 하므로 정답이 생각났다면 빠르게 생각하여 작성하도록 하자. 더 효율적인 코드가 생각났다면 남은 시간에 수정하여 다시 제출하면 되니까

#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;
        
        // temp 를 그대로 자르지 않고 commands 에서 바로 범위지정하여 정렬한다
        sort(temp.begin() + commands[i][0] - 1, temp.begin() + commands[i][1]);
        
        // -2는 -1씩 commands[i][0]-1  +  commands[i][2]-1 에서 -1을 합쳐 쓴 것이다
        // commands[i][0] 를 더하는 이유는 자르지 않고 그대로 쓰기 때문에 자르라는
        // 시작 인덱스를 붙여주어 거기서 부터 [i][2]까지로 범위 지정해서 자른효과를 나타낸것이다
        answer.push_back(temp[commands[i][0] + commands[i][2]-2]);
    }

    return answer;
}