정렬 > 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	commands	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입니다.

 

Solution

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

using namespace std;

int getNumber(const vector<int> &array, const vector<int> &commands) {
    vector<int> contents;
    
    for(int i = commands.at(0); i <= commands.at(1); i++) {
        contents.push_back(array.at(i - 1));
    }
    
    sort(contents.begin(), contents.end());    
    
    return contents.at(commands.at(2) - 1 );
}

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    
    for(auto x : commands) {
        answer.push_back(getNumber(array, x));
    }
    
    return answer;
}

 

남의 코드

#include <functional>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct segment_node {
    int begin, end;
    segment_node* left;
    segment_node* right;
    vector<int> segmentation_array;
};

function<void(vector<int> &, vector<vector<int>> &, vector<int> &)> segment_tree = [](vector<int> &array, vector<vector<int>> &command, vector<int> &answer)
{
    function<bool(const int &, const int &)> cmp = [&](const int &a, const int &b) {
        return array[a] <= array[b];
    };
    vector<int> numbering(array.size(), 0);
    for (int i = 0; i < array.size(); i++) numbering[i] = i;

    int range_begin, range_end, obt, cnt, temp;
    function<void(segment_node*)> segment_search = [&](segment_node* node)
    {
        temp = (node->end - node->begin + 1) / 2;

        if (node->begin == node->end) {
            answer.push_back(array[node->segmentation_array[0]]);
            return;
        }
        else if (node->begin <= range_begin && range_end <= node->begin + temp - 1) {
            if (node->left == NULL) {
                segment_node *left_node;

                left_node = new segment_node;
                left_node->begin = node->begin;
                left_node->end = node->begin + temp - 1;
                left_node->left = NULL;
                left_node->right = NULL;
                left_node->segmentation_array.assign(numbering.begin() + left_node->begin, numbering.begin() + left_node->end + 1);
                sort(left_node->segmentation_array.begin(), left_node->segmentation_array.end(), cmp);
                node->left = left_node;
            }
            segment_search(node->left);
        }
        else if (node->begin + temp <= range_begin && range_end <= node->end) {
            if (node->right == NULL) {
                segment_node *right_node;

                right_node = new segment_node;
                right_node->begin = node->begin + temp;
                right_node->end = node->end;
                right_node->left = NULL;
                right_node->right = NULL;
                right_node->segmentation_array.assign(numbering.begin() + right_node->begin, numbering.begin() + right_node->end + 1);
                sort(right_node->segmentation_array.begin(), right_node->segmentation_array.end(), cmp);
                node->right = right_node;
            }

            segment_search(node->right);
        }
        else
        {
            cnt = 0;
            for (auto &x : node->segmentation_array) {
                if (range_begin <= x && x <= range_end) {
                    cnt++;

                    if (cnt == obt) {
                        answer.push_back(array[x]);
                        return;
                    }
                }
            }
        }
    };

    segment_node* root;
    root = new segment_node;
    root->begin = 0;
    root->end = numbering.size() - 1;
    root->left = NULL;
    root->right = NULL;
    root->segmentation_array = numbering;
    sort(root->segmentation_array.begin(), root->segmentation_array.end(), cmp);

    for (auto &x : command) {
        range_begin = x[0] - 1;
        range_end = x[1] - 1;
        obt = x[2];
        segment_search(root);
    }
};

vector<int> solution(vector<int> array, vector<vector<int>> commands) 
{
    vector<int> answer;//(commands.size(), 0);
    vector<pair<int,int>> arr(array.size(), pair<int,int>());

    for(int i = 0 ; i < array.size() ; i++){
        arr[i].first = array[i];
        arr[i].second = i + 1;
    }

    segment_tree(array, commands, answer);

    return answer;
}

 

후기

어제 새벽 아는 형이 보내 놓은 코딩 테스트 문제를 보고선 아침에 출근하자마자 업무시간 전까지 풀어보았다. 물론 간단히 10분도 안돼서 마무리를 지은 후, 남의 코드를 구경하는데 정말 놀라운 사람을 발견했다. 사과 깎는데 소 잡는 칼을 사용한 느낌? 람다, 재귀, 이진 탐색 등 다양한 기법이 들어갔다. 앞으로 내가 개발자로 업을 이어가면서 이런 코드를 짜야할 날이 올까 싶기도 하다.

 

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