[LeetCode] 1387. Sort Integers by The Power Value

출처: https://leetcode.com/problems/sort-integers-by-the-power-value/

Sort Integers by The Power Value - LeetCode

문제

정수 x의 힘(power)는 다음 규칙을 따라 x를 1로 바꾸는데 필요한 단계의 수로 정의한다.

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

예를 들어, x = 3의 힘은 3이 1이 되는데 7단계(3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)가 필요하기 때문에 7이다.

 

세 정수 lo, hi, 그리고 k가 주어진다. 수행해야할 작업은 [lo, hi]의 모든 정수를 각 정수의 힘을 기준으로 오름차순으로 정렬하는 것이다. 만약 두개 이상의 정수가 동일한 힘을 갖는다면, 원래 순서를 따른다.

 

[lo, hi] 범위의 정수를 힘 순서로 정렬한 뒤 k-th 정수를 반환하라.

예제

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.

Input: lo = 7, hi = 11, k = 4
Output: 7
Explanation: The power array corresponding to the interval [7, 8, 9, 10, 11] is [16, 3, 19, 6, 14].
The interval sorted by power is [8, 10, 11, 7, 9].
The fourth number in the sorted array is 7.

풀이

정수 x의 힘을 구하는 함수를 power(x)라고 하자. 그렇다면 power(x)는 다음의 규칙을 따를 것이다.

• 만약 x가 짝수라면, power(x) = 1 + power(x / 2)
• 만약 x가 홀수라면, power(x) = 1 + power(3 * x + 1)

이를 코드로 만들면 다음과 같다.

function power(x) {
    let step = 0;
    let next_x = x;
    while (next_x != 1) {
        step += 1;
        next_x = next_x & 1 ? 3 * next_x + 1 : next_x / 2;
    }
    return step;
}

이제 범위 [lo, hi]의 모든 정수에 대해서 power(x)를 계산하고 정렬하여 k-th정수에 접근하기 쉽게 하자.

const power_arr = [];
for (let i = lo; i <= hi; i++) {
    power_arr.push({val: i, power: power(i)});
}
power_arr.sort((a, b) => a.power - b.power);

결국에 필요한 값은 k-th 힘을 갖는 정수이기 때문에 배열에 넣을때 객체 형식으로 원래의 값과 같이 저장하여 정렬할때는 힘 값을 사용하여 저장하고 추후에 값을 반환할때는 해당 정수를 반환하도록 하였다.

 

참고로 본래 이 문제의 의도는 DP를 이용한 문제 풀이로 보인다. DP로 변경하면 다음과 같은 코드가 된다.

const m = new Map();
m.set(1, 0)
function power(x) {
  if (m.has(x)) return m.get(x);

  let steps = 1;
  if (x & 1) {
  	steps += power(3 * x + 1);
  } else {
  	steps += power(x / 2);
  }
  m.set(x, steps);
  return steps;
}

다만, 주어진 테스트케이스에서는 DP 방식보다 순수 반복문이 더 빠른 실행시간을 보여주었다.

• DP 방식: 140ms
• 순수 반복문: 116ms

github: 1387.js

opwe37/Algorithm-Study