C++로 거듭제곱 값 기준 정수 정렬하기

정수 x의 거듭제곱 값(power)은 다음 규칙을 반복 적용하여 x를 1로 만들 때까지 필요한 단계 수로 정의됩니다.

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

예를 들어 x = 3일 때의 거듭제곱 값은 7입니다. 3이 1이 되기까지 총 7단계가 필요하기 때문입니다(3 → 10 → 5 → 16 → 8 → 4 → 2 → 1).

문제 설명

정수 lo, hi, k가 주어졌을 때, 구간 [lo, hi]에 속한 모든 정수를 거듭제곱 값을 기준으로 오름차순 정렬해야 합니다. 이때 두 개 이상의 정수가 같은 거듭제곱 값을 가진다면, 해당 정수들을 오름차순으로 정렬합니다. 그런 다음 정렬된 결과에서 k번째에 위치하는 정수를 찾아 반환하면 됩니다.

예를 들어 입력이 lo = 12, hi = 15, k = 2라고 가정해 보겠습니다. 12의 거듭제곱 값은 9, 13의 거듭제곱 값은 9, 14는 17, 15 역시 17입니다. 따라서 정렬된 순서는 [12, 13, 14, 15]가 되고, k = 2이므로 출력값은 13이 됩니다.

풀이 접근 방법

정수 n을 입력받아 거듭제곱 값을 계산하는 getTurn 메서드를 정의합니다.
결과를 저장할 변수 ret := 0으로 초기화합니다.
n이 1이 아닌 동안 다음을 반복합니다.
- n이 홀수이면 n := n * 3 + 1, 짝수이면 n := n / 2
- ret을 1씩 증가시킵니다.
메인 로직에서는 다음과 같이 진행합니다.
lo부터 hi까지의 각 정수 i에 대해 (getTurn(i), i) 형태의 pair를 생성합니다.
생성된 pair를 결과 벡터 ret에 삽입합니다.
pair를 거듭제곱 값 기준으로 정렬하되, 값이 같으면 정수 자체의 오름차순으로 정렬합니다.
정렬된 ret[k - 1]의 두 번째 값(pair의 정수 부분)을 반환합니다.

C++ 구현 예시

아래 코드를 통해 더 명확하게 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector < pair <int, int> > ret;
   static bool cmp(pair <int, int>& a, pair <int, int>& b){
      return a.first == b.first ? a.second < b.second : a.first < b.first;
   }
   int getTurn(int n){
      int ret = 0;
      while(n != 1){
         if(n & 1){
            n = n * 3 + 1;
         }
         else n >>= 1;
            ret ++;
      }
      return ret;
   }
   int getKth(int lo, int hi, int k) {
      for(int i = lo; i <= hi; i++){
         pair <int, int> temp;
         temp.first = getTurn(i);
         temp.second = i;
         ret.push_back(temp);
      }
      sort(ret.begin(), ret.end(), cmp);
      return ret[k - 1].second;
   }
};
main(){
   Solution ob;
   cout << (ob.getKth(12, 15, 2));
}

입력

12
15
2