[PCCP] Lv1: K번째 수(42748) 해설

문제

- 문제 링크: K번째 수

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

 

(C++)

solution 1)

- N: array의 길이

- M: commands의 길이

- commands의 각 원소에 대해 배열을 자르는 시간 복잡도는 O(N)

- 이후 정렬을 포함한 시간 복잡도는 O(NlogN)이고 이를 M번 반복하므로 최종 시간 복잡도는 O(M*(NlogN))

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

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    vector<int> subArray;
    
    for (const auto& cmd : commands) {
        // array에서 각 cmd에 해당하는 영역만 subArray로 복사 후 정렬
        subArray.assign(array.begin() + (cmd[0] - 1), array.begin() + cmd[1]);
        sort(subArray.begin(), subArray.end());
        
        // subArray에서 k번째 answer에 추가
        answer.push_back(subArray[cmd[2] - 1]);
    }
    return answer;
}

solution 2)

#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 (size_t i = 0; i < commands.size() ; ++i){
        vector<int> v;
        for (size_t j = commands[i][0]-1; j < commands[i][1]; ++j){
            v.push_back(array[j]);
        }
        sort(v.begin(), v.end());
        answer.push_back(v[commands[i][2]-1]);
    }
    return answer;
}

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: array의 길이

- M: commands의 길이

- commands의 각 원소에 대해 배열을 자르는 시간 복잡도: O(N)

- 이후 정렬을 포함한 시간 복잡도는 O(NlogN)이고 이를 M번 반복하므로 최종 시간 복잡도는 O(M*NlogN)

import java.util.Arrays;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
        for (int c = 0; c < commands.length; c++) {
            int i = commands[c][0];
            int j = commands[c][1];
            int k = commands[c][2];
            
            // i번째부터 j번째까지 자르기
            int[] slicedArr = Arrays.copyOfRange(array, i - 1, j);
            // 자른 배열을 정렬하기
            Arrays.sort(slicedArr);
            // k번째 원소 구하기
            answer[c] = slicedArr[k - 1];
        }
        return answer;
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: array의 길이

- M: commands의 길이

- commands의 각 원소에 대해 배열을 자르기: O(N)

- 정렬의 시간 복잡도: O(NlogN)

- 모두 M번 반복하므로 최종 시간 복잡도: O((M*N)logN)

def solution(array, commands):
    answer = []
    for cmd in commands:
        i, j, k = cmd
        sliced_arr = array[i - 1 : j] # i번째부터 j번째까지 자르기
        sorted_arr = sorted(sliced_arr) # 자른 배열을 정렬하기
        answer.append(sorted_arr[k - 1]) # k번째 원소 구하기
    return answer

solution 2)

def solution(array, commands):
    answer = []
    for com in commands:
        tmp = sorted(array[com[0]-1:com[1]])
        answer.append(tmp[com[2]-1])
    return answer

solution 3)

import

 

(JavaScript)

solution 1)

- N: array의 길이

- M: commands으 ㅣ길이

- commands의 각 원소에 대해 배열을 자르는 시간 복잡도: O(N)

- 정렬을 포함한 시간 복잡도: O(NlogN)

- 최종 시간 복잡도: O((M*N)lgoN)

function solution(array, commands) {
    const answer = [];
    
    for (const command of commands) {
        const [i, j, k] = command; 
        const sliced = array.slice(i - 1, j); // i부터 j까지 자르기
        sliced.sort((a, b) => a - b); // 자른 배열을 정렬하기
        answer.push(sliced[k - 1]); // k번째 원소 구하기
    }
    
    return answer;
}

solution 2)

import

solution 3)

import