Overview

辞書（Map / Dictionary / HashMap）は、キーと値のペアを管理するデータ構造である。
1.Pythonの辞書の基本
 2.辞書の応用
 3.典型問題を解いてみる

1. Pythonの辞書の基本

Python ではdictを使うとキーと値のペアを簡単に管理できる。
データの管理、検索、カウント、グループ化などに広く使われ、競技プログラミングでは頻度カウント・素早いデータ検索・グループ管理に必須。

操作名	説明	Python の辞書操作
追加・更新	キーに値を設定	`dict[key] = value`
取得（get）	キーの値を取得（キーがない場合も対応）	`dict.get(key, default)`
削除（pop / del）	キーを削除	`dict.pop(key)` / `del dict[key]`
キーの存在確認（in）	キーが辞書に存在するか	`key in dict`
キー一覧（keys）	すべてのキーを取得	`dict.keys()`
値一覧（values）	すべての値を取得	`dict.values()`
キーと値一覧（items）	キーと値のペアを取得	`dict.items()`

＜基本実装＞

# 辞書の作成と基本操作
data = {"apple": 3, "banana": 5, "cherry": 2}

data["banana"] = 7  # 値を更新
data["grape"] = 4  # 新しいキーを追加
print(data.get("orange", 0))  # 存在しないキーの取得（デフォルト値）

del data["apple"]  # キーを削除
print("banana" in data)  # キーの存在確認
print(list(data.keys()))  # キー一覧
print(list(data.values()))  # 値一覧
print(list(data.items()))  # キーと値のペア一覧

計算量について

Python の dict は内部的にハッシュテーブルで実装されており、
キーの検索・追加・更新は平均 $O(1)$ で行える。

そのため、

頻度カウント
高速な存在判定
状態の記録

といった用途で非常に強力である。

2. 辞書の応用

(1) 頻度カウント

リスト内の要素が何回出現したかをカウントする。

from collections import Counter

arr = ["apple", "banana", "apple", "cherry", "banana", "banana"]
counter = Counter(arr)

print(counter)  # Counter({'banana': 3, 'apple': 2, 'cherry': 1})
print(counter["banana"])  # 3

ポイント:

Counter を使うと頻度カウントが簡単
dictでもカウント可能

freq = {}
for item in arr:
    freq[item] = freq.get(item, 0) + 1

(2) 2つのリストを辞書に変換

keys = ["apple", "banana", "cherry"]
values = [3, 5, 2]

fruit_dict = dict(zip(keys, values))
print(fruit_dict)  # {'apple': 3, 'banana': 5, 'cherry': 2}

ポイント:
・zip() を使うとキーと値のペアを簡単に作れる

(3) グループ化

リスト内のデータを特定のキーでグループ化する。

data = [("apple", 3), ("banana", 5), ("apple", 7), ("banana", 2)]
grouped = {}

for key, value in data:
    if key not in grouped:
        grouped[key] = []
    grouped[key].append(value)

print(grouped)  # {'apple': [3, 7], 'banana': [5, 2]}

ポイント:
辞書を使うとカテゴリごとにデータを整理できる

(4) defaultdict を使う

from collections import defaultdict

data = [("apple", 3), ("banana", 5), ("apple", 7)]
grouped = defaultdict(list)

for key, value in data:
    grouped[key].append(value)

print(grouped)  # {'apple': [3, 7], 'banana': [5]}

ポイント:
・キーが存在しないときのデフォルト値を設定できる

※ Counter や defaultdict は、dict をベースにした便利クラスである

3. 典型問題を解いてみる

例題1. 頻度カウント

問題: N 個の単語が与えられる。それぞれの単語が何回登場したかを出力せよ。

参考： ABC155 C - Poll

回答　

from collections import Counter

N = int(input())
words = [input() for _ in range(N)]

counter = Counter(words)
for word, count in counter.items():
    print(word, count)

例題2. キーと値の対応管理

問題: N 個のキーと値のペアが与えられる。辞書を作成し、指定されたキーの値を出力せよ。

回答　

N = int(input())
mapping = {}

for _ in range(N):
    key, value = input().split()
    mapping[key] = value

Q = int(input())
for _ in range(Q):
    query = input()
    print(mapping.get(query, "Not Found"))

例題3. グループ化

問題: N 個のデータが与えられる。それぞれのカテゴリごとにデータをグループ化して出力せよ。

参考： ABC137 C - Green Bin

回答　

N = int(input())
grouped = {}

for _ in range(N):
    category, value = input().split()
    if category not in grouped:
        grouped[category] = []
    grouped[category].append(value)

for category, values in grouped.items():
    print(category, *values)

例題4. 辞書を使った最頻値の検索

問題: N 個の数値が与えられる。最も頻繁に出現する数値を出力せよ。

参考： ABC155 C - Poll

回答　

from collections import Counter

N = int(input())
numbers = list(map(int, input().split()))

counter = Counter(numbers)
most_common = counter.most_common(1)[0][0]  # 最頻値
print(most_common)

例題5. 文字列のカウント

問題: 文字列 S が与えられる。各文字の出現回数を出力せよ。

回答　

from collections import Counter

S = input()
counter = Counter(S)

for char, count in sorted(counter.items()):
    print(char, count)