[프로그래머스 코딩 테스트 고득점 Kit] - 정렬

프로그래머스 코딩테스트 고득점 Kit - 정렬

K번째 큰 수 - level1

문제

주어진 commands에 포함되어 있는 parsing정보를 이용하여 array를 파싱한 데이터를 정렬하여 값을 구하면 되는 간단한 문제

$K: commands의 길이$, $N : Array의 길이$ 라 할 때

총 시간 복잡도는 $O(KNlogN)$가 된다.

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

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    for(const auto& cmd : commands){
        int from = cmd[0], to = cmd[1], kth = cmd[2];
        vector<int> subArray;
        for(int i=from-1; i <= to-1; i++)
            subArray.push_back(array[i]);
        sort(subArray.begin(), subArray.end());
        answer.push_back(subArray[kth-1]);
    }
    return answer;
}

가장 큰 수 - level2

문제

주어진 수를 재배치하여 만들 수 있는 가장 큰 수를 찾는 방법을 먼저 생각해보자.

전체 숫자를 결합하여 만든 숫자를 $s_1s_2s_3s_4...s_n$라고 하자.

이것을 최대화 시키기 위해서는 $s_1 \geq s_2 \geq s_3 \geq ... \geq s_n$이 되어야한다는 것은 자명하다.

이와 같이 정렬하기 위해서 STL sort 알고리즘이 어떤 방식으로 원소들을 정렬하는지에 대한 깊은 이해가 필요하다.

C++의 비교 기반 정렬 알고리즘에서는 다음과 같은 Relation을 만족하는 원소들에 대하여

1. if $a \leq b$ and $b \leq c$ then, $a \leq c$ -> Transitive
2. $_aR_b = \ _bR_a $ -> Symmetric

임의의 2개의 원소의 관계를 비교하여 순서를 결정한다. 최종적으로 정렬의 결과는 Decision Tree의 path를 따라서 결정되므로 우리는 적절하게 비교함수를 재정의 해주면 된다.

Decision Tree에서 우리가 원하는 path로 분기하기 위해서는, 특정 원소를 앞에 덧붙였을 때 와 뒤에 덧붙였을 때를 비교하여 더 큰것을 택함으로서 Greedy하게 접근하여 최적해를 구할 수 있다.

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

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> strNums;
    for(auto num : numbers)
        strNums.push_back(to_string(num));
    auto compare = [](const string& a, const string& b)->bool{
          return a+b > b+a;
    };
    sort(strNums.begin(), strNums.end(), compare);
    for(auto s : strNums)
        answer += s;
    int i = 0;
    while(i < answer.size() - 1 && answer[i] == '0') i++; // 0 처리
    answer = answer.substr(i);
    return answer;
}

H-Index - level2

문제를 결정문제로 치환하여 생각해보자.

$F(m)$: H-index가 m이상일 수 있는가? (true/ false)

우리가 정의한 $F(m)$은 하나의 특정 값 $k$를 기준으로 true/false 값이 변화하는 단조함수의 형태를 가지므로 Parametric Search를 적용할 수 있다.

최적해의 범위가 $[0, 10000]$인 것을 고려하여 해당 범위에서 Parametric Search를 수행해주면 된다.

전체 시간복잡도는 $O(NlogN)$이 된다.

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

int solution(vector<int> citations) {
    int answer = 0, l = 0, r = 10000;
    sort(citations.begin(), citations.end());
    while(l <= r){
        int m = (l + r) / 2, cnt = 0;
        // m이 H-index가 될 수 있는가?
        for(auto item : citations)
            if(item >= m) cnt += 1;
        if(cnt >= m){
            answer = m;
            l = m + 1;
        }else{
            r = m - 1;   
        }
    }
    return answer;
}