[프로그래머스] K번째수

https://programmers.co.kr/learn/courses/30/lessons/42748

코딩테스트 연습 - K번째수

문제 설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

입출력 예

array	command	return
[1, 5, 2, 6, 3, 7, 4]	[[2, 5, 3], [4, 4, 1], [1, 7, 3]]	[5, 6, 3]

입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

 

풀이

해당 문제는 C++같은 경우 vector를 split 한 후 정렬을 진행하면 된다. 보통 <algorithm> 라이브러리를 include하여 정렬을 할 수도 있으나 이번 문제 같은 경우에는 quick_sort를 직접 구현 해 보았다.

 

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

void swap(int &a, int &b){
    
    int temp =a;
    a =b;
    b = temp;
}


void quick_sort(vector<int> &vc, int left, int right){ //퀵 정렬
    
    int pivot = vc[((left+right)/2)];
    int templeft = left;
    int tempright = right;
    
    if(templeft >= tempright) return;
    while(templeft<= tempright){
        
        while(vc[templeft] < pivot) templeft++;
        while(vc[tempright] > pivot) tempright--;
        
        if(templeft <=tempright){
            
            swap(vc[templeft],vc[tempright]);
            templeft++;
            tempright--;
        }
        
    }
    
    quick_sort(vc,left,tempright);
    quick_sort(vc,templeft,right);
    
}

vector<int> split_sort(vector<int> vc, int sp, int lp){
    
    vector<int> tempvc;
    
    for(int i=sp; i<=lp;i++){
        
        tempvc.push_back(vc[i]);
    }
    
    
    quick_sort(tempvc, 0, tempvc.size()-1);
    
    
    //sort(tempvc.begin(), tempvc.end());
    
    return tempvc;
}

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
   
       vector<int> answer;
     
        for(int j=0; j<commands.size();j++) {
            
        int sPoint = (commands[j][0])-1;
        int lPoint = (commands[j][1])-1;
        int checkPoint = (commands[j][2])-1;
 
        vector<int> ttvc = split_sort(array, sPoint, lPoint);        
        
        answer.push_back(ttvc[checkPoint]);
        }
    
    
    return answer;
}

 

끝.