5회 문제풀이 07 / ABC 215 C - One More aab aba baa

ABC 215 C - One More aab aba baa

【문제 개요】

문자열 S의 각 문자를 나열하여 만들 수 있는 문자열을 사전순으로 모두 열거했을때 앞에서부터 K번째에 오는 문자열을 구하시오.
각 문자를 나열하여 만들 수 있는 문자열이란?

• 문자열 A가 문자열 B의 각 문자를 나열하여 만들 수 있는 문자열이다 란, 임의의 문자가 문자열 A와 문자열 B에 동일한 숫자만큼 포함되어있는것을 의미합니다.

힌트 : 순열(permutation)
정렬

【전제】

• 1 ≤ S의 길이 ≤ 8
• S는 영소문자로만 구성되어있다.
• S의 각 문자를 나열하여 만드는 문자열은 K종류 이상 존재한다.

【입력 형태】

S K

【출력 형태】

정답을 출력하라.

【예시】

입력 예 1

aab 2

출력 예 1

aba

문자열 aab의 각 문자로 만들수있는 문자열을 사전순으로 늘어놓으면 aab, aba, baa의 3가지이지만 그 중 2번째는 aba이다.

입력 예 2

baba 4

출력 예 2

baab

입력 예 3

ydxwacbz 40320

출력 예 3

zyxwdcba

출처 : https://atcoder.jp/contests/abc215/tasks/abc215_c