AtCoder-ABC215 C - One More aab aba baa【Python解答例】

AtCoder Beginner Contest215のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 215 - AtCoder

AtCoder Beginner Contest215 C - One More aab aba baa

C - One More aab aba baa

問題文

文字列 S の各文字を並べ替えて作ることが可能な文字列を辞書順にすべて列挙したとき、前から K 番目にくる文字列を求めてください。

制約

・1 ≤ |S| ≤ 8
・S は英小文字のみからなる
・S の各文字を並べ替えてできる文字列は K 種類以上存在する

解答例

import itertools

s, k = input().split()

k = int(k)

res = set()
for nums in itertools.permutations(range(len(s))):
    tmp = ""
    for i in range(len(nums)):
        tmp = tmp + s[nums[i]]
    res.add(tmp)

ans = list(res)

ans.sort()

print(ans[k-1])

解説

文字列Sを並び替えてできる文字列をすべて辞書順に列挙したときに、K番目の文字列がなにか答える問題です。

Sが最大で8文字と少ないので順列全探索で作成できる文字列を列挙しました。

順列について過去に勉強した記事はこちら
ebisuke33.hatenablog.com

itertoolsでSの文字数までの順列を作成しnumsとしました。
numsにしたがってSから順番に文字を抜き取っていき、tmpに加えていきます。
tmpが完成したらresに追加しました。

このとき、重複する可能性があるのでresはset型としています。

探索を終えた後にソートするためset型のresを配列ansに変換しました。

ソートした後でansのk-1番目の要素を出力すればACでした。

ABC215の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com