문제
s의 문자로 만들 수 있는 모든 배열을 사전순으로 나열합니다. "abc"라면 abc, acb, bac, bca, cab, cba입니다. 1부터 셀 때 k번째 항목을 반환하세요. 문자가 12개이면 배열이 479,001,600개나 되어 전부 만들기에는 너무 느립니다. 같은 문자로 시작하는 배열의 묶음에는 (length − 1)!개의 항목이 있으므로, 한 번에 한 문자씩 골라 나갈 수 있습니다.
lexicographic_permutation(s, k) 함수를 구현하세요.
입력
s: 임의의 순서로 주어진 서로 다른 문자들입니다.
k: 정렬된 목록에서의 위치이며 1부터 셉니다.
출력
k번째 배열을 문자열로 반환합니다. 문자는 문자 코드로 비교하므로 숫자가 대문자보다 앞에 오고, 대문자가 소문자보다 앞에 옵니다.
제약 조건
1 ≤ s.length ≤ 12; s의 모든 문자는 서로 다릅니다; 1 ≤ k ≤ s.length!
예시
입력:
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";
설명
목록은 abc, acb, bac, bca, cab, cba이고 네 번째는 "bca"입니다.
입력:
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";
설명
첫 번째 배열은 문자를 정렬한 순서 그대로이므로 "123"입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
먼저 문자들을 정렬하세요.
힌트 2
첫 문자를 하나 정하면 (length − 1)!개의 순열이 정해지므로, k − 1을 그 수로 나누면 첫 문자를 고를 수 있습니다.
힌트 3
고른 문자를 제거하고 나머지를 유지한 채 남은 문자들로 반복하세요.
예상 복잡도
시간 O(n²), 추가 공간 O(n)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.