SRM627Div1Easy
問題
長さN()の文字列が与えられる。その中で違う文字同士のペアを取り出す。取り出すペアが無くなった時点で終了となり、この時に残っている文字をwinning letterと呼ぶ。winning letterの文字列を辞書順にして求めよ。
解法
サイズが小さいので一文字ずつwinning letterになるかを確認することができる。確認の処理は出現回数が多い文字を2つ取り出しそれぞれから1を引くという処理をして、最後に残った数字と注目してる文字の出現回数を比較することで実現できる。
実装が簡単になるのでpriority_queを使用している。
計算量
N: 文字列の長さ
M: アルファベットの数(a-zの26文字)
: 文字の全探索
: 確認の処理
: priority_que(Binary Search Tree)の挿入コスト