Dictionary と Set

読了目安 約3分

集計は dict[key, default:0] += 1 の一行。存在判定は Set でほぼ一定時間にする。

「この値は何回出てきたか」「この値はもう見たか」。 この 2 つの問いに一瞬で答えるのが Dictionary と Set です。

Dictionary

辞書 (Dictionary) は、キーで値を引けるコレクションです。 型は [キーの型: 値の型] と書き、[:] が空の Dictionary です。

var stock: [String: Int] = [:]
stock["apple"] = 3
stock["banana"] = 5
print(stock["apple"]!)
print(stock["cherry"] == nil)

存在しないキーを引くと nil が返ります。 確実にあると分かっているキーは ! を付けて取り出します。

集計のイディオム

添字に default: を付けると、キーがないときに使う値を指定できます。 「回数を数える」処理は、これで 1 行になります。

var count: [String: Int] = [:]
for word in ["apple", "banana", "apple"] {
    count[word, default: 0] += 1
}
print(count["apple", default: 0])
print(count["cherry", default: 0])

count[word, default: 0] += 1 は競プロ最頻出のイディオムです。 そのまま手に覚えさせてください。

Set

集合 (Set) は、重複しない値の集まりです。 insert で追加し、contains で有無を調べます。

var seen: Set<Int> = []
seen.insert(3)
seen.insert(5)
seen.insert(3)
print(seen.count)
print(seen.contains(5))
print(seen.contains(4))

同じ値を 2 回入れても 1 個のままです。

配列との使い分け

配列の contains は、先頭から順に全要素を調べます。 Dictionary と Set はハッシュ表という仕組みで、要素数によらずほぼ一定時間で探せます。

10^5 個の値それぞれに配列の contains を呼ぶと、比較は最大 10^10 回になり間に合いません。 「あるかどうか」を何度も聞くなら Set に置き換えてください。

順序は不定

Dictionary と Set に、中身の並び順の保証はありません。 for-in で取り出す順番は、実行のたびに変わりえます。 順に出力したいときは、キーをソートしてから使います。

let count = ["banana": 2, "apple": 1, "cherry": 3]
for key in count.keys.sorted() {
    print(key, count[key]!)
}

試してみよう: .sorted() を消して何度か実行し、順番が安定しないことを確かめてください。

学びどころ

演習

1 行目に整数 N が入力されます。 2 行目に N 個の整数 A_1 … A_N が空白区切りで入力されます。

最も多く現れる値と、その回数を空白区切りで 1 行に出力してください。 最も多く現れる値が複数あるときは、そのうち最小の値を選びます。

制約: 1 ≤ N ≤ 10^5、1 ≤ A_i ≤ 10^9

入力例:
5
1 2 2 3 2

出力例:
2 3

_ = readLine()
let a = readLine()!.split(separator: " ").map { Int($0)! }

var count: [Int: Int] = [:]
for x in a {
    count[x, default: 0] += 1
}

var bestValue = 0
var bestCount = 0
for (value, c) in count {
    if c > bestCount || (c == bestCount && value < bestValue) {
        bestValue = value
        bestCount = c
    }
}
print(bestValue, bestCount)