[LeetCode] - 1387. Sort Integers by the Power Value

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '중간 (Medium)' 단계인 "Sort Integers by the Power Value" 문제입니다.

--> https://leetcode.com/problems/sort-integers-by-the-power-value/description/

 

문제 : 

The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps :

• if x is even then x = x / 2
• if x is odd then x = 3 * x + 1

For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1).

 

Given three integers lo, hi and k. The task is to sort all integers in the interval [lo, hi] by the power value in ascending order, if two or more integers have the same power value sort them by ascending order.

 

Return the kth integer in the range [lo, hi] sorted by the power value.

 

Notice that for any integer x (lo <= x <= hi) it is guaranteed that x will transform into 1 using these steps and that the power of x is will fit in a 32-bit signed integer.

---

Example 1:

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.

 

Example 2 :

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.

 

Constraints :

• 1 <= lo <= hi <= 1000
• 1 <= k <= hi - lo + 1

---

이 문제에서의 정수 x의 파워는 x를 1로 변환하기 위해 필요한 단계 수로 정의됩니다. 주어진 구간 [lo, hi]의 모든 정수를 파워 값 기준으로 오름차순 정렬한 후 k번째 정수를 반환하는 문제입니다. 동일한 파워 값을 가진 경우, 정수 자체의 값에 따라 오름차순으로 정렬합니다.

class Solution {
    public int getKth(int lo, int hi, int k) {
        Map<Integer, Integer> powerMap = new HashMap<>();
        
        for (int i = lo; i <= hi; i++) {
            powerMap.put(i, steps(i));
        }
        
        List<Map.Entry<Integer, Integer>> sortedList = new ArrayList<>(powerMap.entrySet());
        sortedList.sort((entry1, entry2) -> {
            int valueCompare = entry1.getValue().compareTo(entry2.getValue());
            if (valueCompare == 0) {  // If values are the same, compare by keys
                return entry1.getKey().compareTo(entry2.getKey());
            }
            return valueCompare;  // Otherwise, compare by values
        });

        
        
        return sortedList.get(k - 1).getKey();  // Access by index directly from sorted list
        
    }


    private static int steps(int x) {
        int stepNum = 0;
        while (x != 1) {
            if (x % 2 == 0) {
                x = x / 2;
                stepNum++;
            } else {
                x = 3 * x + 1;
                stepNum++;
            }
        }
        return stepNum;
    }
}

 

제 코드는 막상 돌려보니 비효율적이었습니다. 그래도 제 아이디어가 뭐였는지라도 설명드리겠습니다 : 

1. 파워 값 계산 및 저장 :
   • 주어진 범위 [lo, hi]의 각 정수에 대해 파워 값을 계산하고 이를 맵에 저장합니다.
2. 맵 엔트리를 리스트로 변환 및 정렬 :
   • 맵의 엔트리를 리스트로 변환하고, 파워 값을 기준으로 정렬합니다. 파워 값이 동일한 경우 정수 값으로 정렬합니다.
3. k번째 정수 반환 :
   • 정렬된 리스트에서 k번째 정수를 반환합니다.

시간 및 공간 복잡도 : 

1. 시간 복잡도 :
   • 파워 값을 계산하는 데 O(log x) 시간이 소요됩니다. 모든 정수에 대해 이 작업을 수행하므로 총 시간은 O((hi - lo + 1) * log x)입니다.
   • 정렬하는 데 O(n log n) 시간이 소요됩니다. 여기서 n은 [lo, hi] 구간의 크기입니다.
   • 따라서 전체 시간 복잡도는 O(n log n)입니다. (여기서 n = hi - lo + 1)
2. 공간 복잡도 :
   • 맵과 리스트를 사용하는 데 O(n) 공간이 필요합니다.

---

다른 유저들은 어떻게 했나 궁금해서 서핑하다가 정말 좋은 솔루션 하나를 발견해서 공유해보고자 합니다 : 

 

satYaDcoder 님의 코드 : 

class Solution {
    
    HashMap<Integer, Integer> cache;
    public int getKth(int lo, int hi, int k) {
        cache = new HashMap();
        

        PriorityQueue<Item> maxHeap = new PriorityQueue<Item>((a, b) -> (a.power == b.power) ? (b.num - a.num) : (b.power - a.power));
        
        for(int num = lo; num <= hi; num++){
            //get the power of each num
            //store in maxheap
            maxHeap.add(new Item(num, getPower(num)));
            
            //if heap size beacome greater than k
            if(maxHeap.size() > k){
                //just remove item with maximum power
                maxHeap.remove();
            }
        }
        
        return maxHeap.remove().num;
    }
    
    private int getPower(int n){
        if(n == 1) return 0;
        
        //retrieve from cache
        if(cache.containsKey(n)) return cache.get(n);
        
        int power = 1 + ((n % 2 == 0) ?  getPower(n / 2) : getPower((3 * n) + 1));
        
        //save in cache
        cache.put(n, power);
        
        return power;
    }
}

class Item {
    int num;
    int power;
    
    public Item (int num, int power){
        this.num = num;
        this.power = power;
    }
}

 

이 사람의 코드는 좀 더 길고 객체지향적이지만 제가 브레이크 다운 해보겠습니다 : 

 

이 코드는 주어진 범위 [lo, hi]의 정수에 대해 각 정수의 파워 값을 계산하고, 이 값을 기준으로 정수를 정렬하여 k번째 정수를 반환합니다. 여기서 파워 값은 주어진 규칙에 따라 계산됩니다. 파워 값을 계산할 때 이미 계산된 값을 저장하여 캐시를 사용해 중복 계산을 줄입니다. 최대 힙(PriorityQueue)을 사용하여 상위 k개의 요소만 유지하여 효율적으로 정렬을 수행합니다.

1. 캐시 초기화:
   • 파워 값을 저장할 캐시를 초기화합니다.
2. 최대 힙 사용:
   • 최대 힙을 사용하여 파워 값 기준으로 정렬합니다. 파워 값이 같으면 정수 값을 기준으로 정렬합니다.
3. 범위 내의 모든 정수에 대해 파워 값 계산 및 최대 힙에 추가:
   • 각 정수의 파워 값을 계산하여 최대 힙에 추가합니다.
   • 힙의 크기가 k를 초과하면 최대 파워 값을 가진 항목을 제거합니다.
4. k번째 정수 반환:
   • 힙에서 제거된 k번째 정수를 반환합니다.
5. 파워 값 계산 및 캐싱:
   • 재귀적으로 파워 값을 계산하고 캐시에 저장하여 중복 계산을 줄입니다.

시간 및 공간 복잡도:

1. 시간 복잡도:
   • 파워 값을 계산하는 데 O(log n) 시간이 소요됩니다. 모든 정수에 대해 이 작업을 수행하므로 총시간은 O((hi - lo + 1) * log n)입니다.
   • 최대 힙에 요소를 추가하고 제거하는 작업은 O(log k) 시간이 소요됩니다. 이 작업을 hi - lo + 1번 수행하므로 총시간은 O((hi - lo + 1) * log k)입니다.
   • 따라서 전체 시간 복잡도는 O((hi - lo + 1) * (log n + log k))입니다.
2. 공간 복잡도:
   • 캐시와 최대 힙에 저장된 요소의 수는 O(hi - lo + 1)입니다.
   • 따라서 전체 공간 복잡도는 O(hi - lo + 1)입니다.

이 코드는 효율적으로 파워 값을 계산하고, 최대 힙을 사용하여 k번째 정수를 찾는 문제를 해결합니다.

---

내 코드와 다른 유저의 코드 Runtime 결과