Leetcode - 1387. Sort Integers by The Power Value

문제

값 x 주어질때 power값은 아래의 규칙을 따라 x가 1 이될때 까지의 step수를 의미한다.

• x가 짝수면 x = x / 2
• x가 홀수면 x = 3 * x + 1

예를 들어 x = 3 이면 power값은 7이다. (3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1).

[lo, hi] 범위의 x값들이 주어질때. k 번째로 작은 power값의 x값은?

Input: lo = 12, hi = 15, k = 2
Output: 13
Explanation: The power of 12 is 9 (12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)
The power of 13 is 9
The power of 14 is 17
The power of 15 is 17
The interval sorted by the power value [12,13,14,15]. For k = 2 answer is the second element which is 13.
Notice that 12 and 13 have the same power value and we sorted them in ascending order. Same for 14 and 15.

해결 dp top-down , O(nlogn)

특정 값의 power값은 모두 동일하므로 power값을 계산할때 memoization 하면 빠르게할수 있다. 그리고 계산 구조는 재귀적인 구조이다.

std::priority_queue 에 대해 새로 배운 것들

• priority_queue는 기본적으로 max heap이다. 이 문제에서는 min heap이어야하므로, 맨 마지막 인자에 greater<pair<int, int>> 를 추가한다. 이게 없으면 max heap.
• priority_queue는 pair자료형에서 first값을 기준으로 정렬한다.

class Solution {
    int power_of_num(int val, int *dp) {
        if (val == 1)
            return 0;
        if (dp[val])
            return dp[val];
        if (val % 2 == 0)
            dp[val] = power_of_num(val / 2, dp) + 1;
        else
            dp[val] = power_of_num(val * 3 + 1, dp) + 1;
        return dp[val];
    }
public:
    int getKth(int lo, int hi, int k) {
        int ret = 0;
        int dp[1000001] = {0};
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
        for (int i = lo; i <= hi; i++)
            pq.push(make_pair(power_of_num(i, dp), i));
        while (k--) {
            ret = pq.top().second;
            pq.pop();
        }
        return ret;
    }
};