파이썬에서 k번째로 작은 n 길이 사전순으로 가장 작은 문자열을 찾는 프로그램

<시간/>

숫자 n과 다른 값 k가 있다고 가정합니다. 이제 문자가 연속적으로 반복되지 않는 "0", "1" 및 "2"만 포함하는 문자열을 고려해 보겠습니다. 길이가 n인 문자열을 선택하고 사전순으로 가장 작은 k번째 문자열을 찾아야 합니다. k번째 문자열이 없으면 빈 문자열을 반환합니다.

따라서 입력이 n =4 k =2와 같으면 출력은 "0120"이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

s, k 및 last가 소요되는 solve() 메소드 정의
s가 0과 같으면
- 빈 문자열 반환
"012"의 각 문자 c에 대해 다음을 수행합니다.
- c가 last와 같으면
  - 다음 반복으로 이동
- k <2^(s-1)이면
  - return c + solve(s - 1, k, c)
- k :=k - 2^(s-1)
빈 문자열 반환
메인 메소드 호출에서 solve(n, k, Null)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예시 코드

class Solution:
   def solve(self, s, k, last=None):
      if s == 0:
         return ""
         for c in "012":
            if c == last:
               continue
            if k < 2 ** (s - 1):
               return c + self.solve(s - 1, k, c)
            k -= 2 ** (s - 1)
         return ""

ob = Solution()
n = 4
k = 2
print(ob.solve(n, k))

입력

4, 2