[LeetCode] 440. K-th Smallest in Lexicographical Order

https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/description/?envType=daily-question&envId=2024-09-22

leetcode - K-th Smallest in Lexicographical Order

문제 유형 : 트리, dfs, 수학

문제 난이도 : Hard

 

문제

Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].

 

두 개의 정수 n과 k가 주어진다. 범위 [1,n]에서 사전순으로 k번째로 작은 정수를 반환하시오.

 

풀이

순차적으로 k개를 찾는 것은 느리다.

대신, 점프를 할 필요가 있다.

위 그림에서는 1에서 2로 넘어가기 위해서 사이에 수가 얼마나 있는지를 구하는 모습이다.

보면, 두 개의 접두사가 사용된다. 가장 높은 자릿수 두 개가 사용된다.

적은 쪽의 접두사에서 큰 쪽의 접두사 수까지 사이에 얼마나 수가 있는지를 구하는 방법은,

두 접두사에 10을 곱해보면서 자릿수를 늘리면서 차이를 계속 구하며 누적하는 것이다.

 

 

위의 동작을 구현하는 함수를 만들고, 현재 prefix에서 다음 prefix까지 넘어갈 횟수를 look-ahead할 수 있다.

메인에서, 접두사는 1로 시작한다.

k가 0보다 큰동안 다음을 할 수 있다:

  현재 카운트 + look-ahead값이 k보다 작으면 계속해서 탐색하고, 크다면 접두사에 10을 곱해서 더 작은 단위로 접두사를 쪼갠다.

최종적으로 남은 접두사를 반환하면 된다.

 

 

코드

C++

class Solution {
private:
    int countSteps(int n, long prefix1, long prefix2) {
        int steps = 0;
        while(prefix1 <= n) {
            steps += min((long)(n+1), prefix2) - prefix1;
            prefix1 *= 10;
            prefix2 *= 10;
        }
        return steps;
    }
public:
    int findKthNumber(int n, int k) {
        int curr = 1;
        k--;

        while(k > 0) {
            int step = countSteps(n, curr, curr+1);
            if(step <= k) {
                curr++;
                k -= step;
            } else {
                curr *= 10;
                k--;
            }
        }

        return curr;
    }
};