[Programmers] 42748번 - K번째수 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 배열 array에 대해 i 번째 숫자부터 j 번째 숫자까지 자르고 정렬했을 때, k 번째에 있는 수를 구하는 문제다. 각 쿼리들이 원본 배열에 대해 수행되기 때문에 주어진 원본 배열 자체를 정렬할 경우 이후 쿼리들이 이전 쿼리의 영향을 받게 되어 원본 배열은 수정하면 안된다.

---

2. 코드

1. 풀이 [Java]

복사할 구간의 길이만큼을 배열의 길이로 갖는 tmp라는 임시 배열을 매번 생성한 후, tmp에 주어진 구간을 복사하여 정렬하는 방식으로 해결했다. 배열 간 복사를 빠르게 할 수 있는 System.arraycopy 메서드를 활용하여 메모리 고속 복사를 수행한 후 정렬하고 k 번째 수를 구하는 방식으로 해결했다.

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] ans = new int[commands.length];

        for (int i = 0; i < commands.length; i++) {
            int start = commands[i][0] - 1;
            int end = commands[i][1] - 1;
            int k = commands[i][2] - 1;

            int[] tmp = new int[end - start + 1];
            System.arraycopy(array, start, tmp, 0, tmp.length);
            Arrays.sort(tmp);

            ans[i] = tmp[k];
        }

        return ans;
    }
}

2. 풀이 [C++]

벡터에서 이터레이터를 받아서 새로운 벡터를 생성하는 생성자를 활용했다. 해당 구간에 대한 벡터를 생성 후 정렬하면 k 번째 수를 간단하게 알 수 있다.

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

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> ans;

    for (auto& c : commands) {
        int s = c[0];
        int e = c[1];
        int k = c[2];

        vector<int> tmp(array.begin() + s - 1, array.begin() + e);
        sort(tmp.begin(), tmp.end());
        ans.push_back(tmp[k - 1]);
    }

    return ans;
}

---