문제

Programmers, K번째수

핵심

• 입력의 크기가 $10^2$이하이므로 구현에 집중한다.
• 배열 array가 주어지고, i번째 수부터 j번째 수까지 자르고 정렬한 뒤 k번째 수를 구해야 한다. i,j,k 인자가 2차원 배열로 주어지는 데 인덱스를 신경 쓰며 파싱하면 된다.
• 임시 배열 sliced를 만들어 i ~ j 범위에 속하는 숫자를 채워 넣은 뒤에 정렬하여 k번째 수를 출력하는 식으로 구현하였다.

개선

코드

시간복잡도

• $O(N^2)$

C++

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

Java

import java.util.ArrayList;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        int idx = 0;
        for (int i = 0; i < commands.length; ++i) {
            ArrayList<Integer> sliced = new ArrayList<>();
            for (int j = commands[i][0] - 1; j < commands[i][1]; ++j)
                sliced.add(array[j]);
            sliced.sort((a, b) -> a.compareTo(b));
            answer[idx++] = sliced.get(commands[i][2] - 1);
        }
        return answer;
    }
}