모든 챌린지
보통 0명 해결 정답률 0%

Lexicographic Permutation

Find the k-th arrangement of some distinct characters in dictionary order.

배우게 될 내용

  • Skip whole blocks of permutations at once
  • Convert a rank to a permutation
  • Work with 0-based and 1-based positions

문제

번역본 보기

List every arrangement of the characters of s in dictionary order. For "abc" the list is abc, acb, bac, bca, cab, cba. Return the k-th entry, counting from 1. Generating the whole list is too slow for 12 characters (479,001,600 arrangements): each block of arrangements that starts with the same character has (length − 1)! entries, so you can pick one character at a time.

Implement lexicographic_permutation(s, k).

Input

s: Distinct characters in any order.

k: The position in the sorted list, counting from 1.

Output

Return the k-th arrangement as a string. Characters are compared by their character codes, so digits come before uppercase letters, which come before lowercase letters.

제약 조건

1 ≤ s.length ≤ 12; all characters of s are distinct; 1 ≤ k ≤ s.length!

예시

예시 1
입력:
s = "abc"
k = 4

예상 출력:
expected = "bca"
입력:
std::string s = "abc";
long long k = 4;

예상 출력:
std::string expected = "bca";
입력:
string s = "abc";
long k = 4;

예상 출력:
string expected = "bca";

설명

The list is abc, acb, bac, bca, cab, cba, and the fourth is "bca".

예시 2
입력:
s = "312"
k = 1

예상 출력:
expected = "123"
입력:
std::string s = "312";
long long k = 1;

예상 출력:
std::string expected = "123";
입력:
string s = "312";
long k = 1;

예상 출력:
string expected = "123";

설명

The first arrangement is the characters in sorted order: "123".

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

Sort the characters first.

힌트 2

Each choice of first character covers (length − 1)! permutations, so dividing k − 1 by that number picks it.

힌트 3

Remove the chosen character, keep the remainder, and repeat with the rest.

예상 복잡도

O(n²) time, O(n) extra space

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.