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

문제

- 문제 링크: K번째 수

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#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 2)

#include<>

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