はじめに

今回はyukicoderのNo.69をPython3で解いてみました。

問題URL

一般的な考え方

2つの文字列 A, Bのうち、Aを自由に並び替えたとき、Bと一致させられるか。という問題です。問題の定義には、

・どちらも等しい長さ
・すべて小文字のアルファベットからなる

とあります。ここからAとBに含まれる文字が一致しなければ、Aを並び替えてもBにならないことがわかります。このような場合、AをソートしてBと一致するかどうか調べるのが一般的な解き方だと思います。
_{(なんでこのやり方浮かばなかったんだろう…。)}

実装例

69.py

A = str(input().rstrip())
B = str(input().rstrip())

A = sorted(A)
B = sorted(B)

if A == B:
    print("YES")
else:
    print("NO")

まあこんな感じです。提出してみたところ、実行時間は18ms、使用メモリは7776KBでした。
Pythonで文字列をソートする場合、リスト型のメソッドであるsort()ではなく、組み込み関数のsorted()を使うのがポイントです。

ソートを使わない考え方

ここからが本題です。私が先に思いついたのはこの考え方でした。
この問題の実行時間制限は5.000秒/ケース、メモリ制限は512MBなので、これを満たせば、ソートを使う方法と比べて重くても遅くてもACになります。
私の頭の中には、並び替え=アナグラム という考えが浮かびました。

具体的にいうと、Aを並び替えてできる文字列全てとBを比較し、一致するか調べるというものです。

使ったもの

Pythonには標準ライブラリにitertoolsというモジュールがあります。
・itertools --- 効率的なループ実行のためのイテレータ生成関数 — Python 3.9.4 ドキュメント
これはイテレータ生成関数であり、組み合わせや順列関連の処理を高速に行うことができます。Python競プロ界隈では結構有名なのではないでしょうか。今回はそのうち、組み合わせイテレータであるitertools.permutations()を用いました。以下に使用例を示します。

import itertools
A = "cap"

for v in itertools.permutations(A):
    print(v)

# ('c', 'a', 'p')
# ('c', 'p', 'a')
# ('a', 'c', 'p')
# ('a', 'p', 'c')
# ('p', 'c', 'a')
# ('p', 'a', 'c')

このように、for文で文字列のアナグラムを簡単に生成することができます。
また、以下のようにリスト内包表記を用いることで、全ての並び替え例を1つのリストにまとめることができます。

import itertools
A = "cap"

anagramable = ["".join(v) for v in itertools.permutations(A)]
print(anagramable)
# ['cap', 'cpa', 'acp', 'apc', 'pca', 'pac']

実装例

69(anotherSolution).py

import itertools
A = str(input().rstrip())
B = str(input().rstrip())

anagramable = ["".join(v) for v in itertools.permutations(A)]

if B in anagramable:
    print("YES")
else:
    print("NO")

私が実際に提出したコードです。実行時間は1628ms、使用メモリは267416KBでした。ソートを使う方法とは比べものにならないほど遅く、処理も重いですがACになりました。

おわりに

同様の問題、割とよく見かけるので、ソートを使うことを覚えていればなんとかなる場合が多そうだと思いました。_{ちなみに、私は解説を見るまでソートを使えばいいと気づきませんでした。合掌。}

この記事で用いたコードを含め、yukicoderやAtCoderに提出したコードは、Githubにアップロードしています。気になる方はこちらからどうぞ↓
・for_yukicoder — Github/PyRadiolarus
・for_AtCoder — Github/PyRadiolarus

【yukicoder解説】〜Python3で「No.69 文字を自由に並び替え」をソートを使わずに解いてみた〜

目次