はじめに
みなさん座標圧縮（略して座圧）という言葉はご存じですか、私はつい最近知りました。というのも以下の操作に「座標圧縮」という立派な名前がついていると知らなかったんですよね。
例えば下のような配列Aがあったとき
A = [4, 90, 25, 30, 30, 8, 90, 90]
これを座標圧縮するというのは配列の各数字が何番目に大きいかを1から1順にナンバリングしていくという操作です。つまり配列Aに座標圧縮を施すと
A_zaatsu = [1, 5, 3, 4, 4, 2, 5, 5]
となります。ただし配列Aのなかで同じ数字はA_zaastuの中でも同じ数字が割り当てられることに注意してください。今回はこの座標圧縮という処理を簡単に書けるようになろうというのが本題です。
いざ本題
もう最初に答えを書いちゃいます。座標圧縮はこう書けば簡単です。
A = [4, 90, 25, 30, 30, 8, 90, 90]
S = sorted(list(set(A)))
ranking = {x:i+1 for i,x in enumerate(S)}
A_zaatsu = []
for a in A:
A_zaatsu.append(ranking[a])
print(A_zaatsu) ## [1, 5, 3, 4, 4, 2, 5, 5]
はい、いかがでしょう。何をしているかを説明します。
このコードで肝となるのは「Aの各要素が小さいほうから何番目なのかを知りたい！」ということです。今回のコードではそれがrankingにあたります。Aの各要素aに対してranking[a]はaが配列Aの中で小さいほうから何番目かを表しています。
そのrankingをつくるにあたってSという、Aから重複を取り除いて昇順ソートした配列を用意しています。
ここまでの説明を踏まえてもう一度コードを見てみましょう。
A = [4, 90, 25, 30, 30, 8, 90, 90]
S = sorted(list(set(A))) ## [4, 8, 25, 30, 90]
ranking = {x:i+1 for i,x in enumerate(S)} ## {4: 1, 8: 2, 25: 3, 30: 4, 90: 5}
A_zaatsu = []
for a in A:
A_zaatsu.append(ranking[a])
print(A_zaatsu) ## [1, 5, 3, 4, 4, 2, 5, 5]
「Aの各要素が小さいほうから何番目なのかを知りたい！」という気持ちになれば自然に理解できると思います。最後まで読んでいただきありがとうございました。
おまけ
座標圧縮の手法がつかえる問題を貼っておきます。
C - 座圧
C - Reorder Cards
-
もちろん1からじゃなくてもいいです。そのあたりは問題に合わせて適宜変更してください。 ↩