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

사전순 순열

서로 다른 문자들의 배열 중 사전순으로 k번째 배열을 찾습니다.

배우게 될 내용

  • 순열의 묶음을 통째로 건너뛸 수 있다
  • 순위를 순열로 변환할 수 있다
  • 0부터 세는 위치와 1부터 세는 위치를 다룰 수 있다

문제

원문 보기 (영어)

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!

예시

예시 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";

설명

목록은 abc, acb, bac, bca, cab, cba이고 네 번째는 "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";

설명

첫 번째 배열은 문자를 정렬한 순서 그대로이므로 "123"입니다.

접근 방법

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

힌트 1

먼저 문자들을 정렬하세요.

힌트 2

첫 문자를 하나 정하면 (length − 1)!개의 순열이 정해지므로, k − 1을 그 수로 나누면 첫 문자를 고를 수 있습니다.

힌트 3

고른 문자를 제거하고 나머지를 유지한 채 남은 문자들로 반복하세요.

예상 복잡도

시간 O(n²), 추가 공간 O(n)

참고 자료

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

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

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

다른 사람의 풀이 보기

커뮤니티 솔루션

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