《アルゴリズムを学ぶ》9.Set（集合）

# Overview
set（集合）は 重複のないデータ管理 を効率的に行うためのデータ構
[1.セットの基本](#1-セットの基本)
[2.セットの集合演算](#2-セットの集合演算)
[3.セットの応用](#3-セットの応用)
[4.典型問題を解いてみる](#4-典型問題を解いてみる)

# 1. セットの基本
リストとは異なり、順序を持たず、高速な検索・追加・削除が可能。
特に、データの一意性を保証する場面や、数学的な集合演算（和・交差・差分など） で役立つ。

|操作名|説明|Python のセット操作|
|---|---|---|
|追加（add）|要素をセットに追加  |`set.add(x)` |
|削除（remove / discard） |要素を削除 |`set.remove(x)` / `set.discard(x)` |
|検索（in） |要素が存在するか  |`x in set` |
|サイズ取得（len） |セットのサイズ |`len(set)` |
|クリア（clear） |セットを空にする |`set.clear()`|

ポイント:
`remove(x)` は要素がなければエラーになる
`discard(x)` は要素がなくてもエラーにならない

**＜基本実装＞**
```python
my_set = {1, 2, 3}
my_set.add(4)        # 追加
my_set.remove(2)     # 削除
print(3 in my_set)   # 存在確認
print(len(my_set))   # サイズ取得
```

# 2. セットの集合演算
|操作名	|説明	|Python のセット操作|
|---|---|---|
|和集合（union）	|2つの集合のすべての要素	|`A \| B`
|積集合（intersection）	|共通する要素のみ	|`A & B` または `A.intersection(B)`
|差集合（difference）	|Aに含まれるがBに含まれない要素	|`A - B` または `A.difference(B)`
|対称差（symmetric_difference）|AとBのどちらかにあるが共通しない要素	|`A ^ B` または `A.symmetric_difference(B)`

**＜基本実装＞**
```Python
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

print(A | B)  # 和集合 {1, 2, 3, 4, 5, 6}
print(A & B)  # 積集合 {3, 4}
print(A - B)  # 差集合 {1, 2}
print(A ^ B)  # 対称差 {1, 2, 5, 6}
```
ポイント:
・データの集合演算が簡単にできる
・特定のデータがどの集合に属するかをすぐに判定可能

# 3. セットの応用
### (1) リストの重複削除
```python
lst = [1, 2, 2, 3, 4, 4, 5]
unique_lst = list(set(lst))  # [1, 2, 3, 4, 5]
```
ポイント:
リストを `set` に変換すると自動で重複が削除される

### (2) 2つのリストの共通要素を取得
```python
list1 = [1, 2, 3, 4]
list2 = [3, 4, 5, 6]

common_elements = list(set(list1) & set(list2))  # [3, 4]
```
ポイント:
セットの積集合を使うと高速に共通要素を取得できる

### (3) 数列の出現回数を一意にカウント
```python
numbers = [3, 3, 5, 7, 5, 5, 9, 3]
unique_numbers = set(numbers)
print(len(unique_numbers))  # 4（{3, 5, 7, 9}）
```
ポイント:
異なる値の種類を数えるのに`set` は便利

# 4. 典型問題を解いてみる

### 例題1. リストの重複を除去
**問題: N 個の整数が与えられる。異なる値の数を出力せよ。**
> [参考： ABC315 B - Unique Count](https://atcoder.jp/contests/abc315/tasks/abc315_b)
<details><summary> 回答　</summary>

```python
N = int(input())
A = list(map(int, input().split()))

print(len(set(A)))
```
</details>

### 例題2. 2つのリストの共通要素
**問題: 2つの整数リスト A, B が与えられる。共通する要素を昇順で出力せよ。**
> [参考： ABC318 B - Common Elements](https://atcoder.jp/contests/abc318/tasks/abc318_b)
<details><summary> 回答　</summary>

```python
N = int(input())
A = set(map(int, input().split()))
M = int(input())
B = set(map(int, input().split()))

print(*sorted(A & B))
```
</details>

### 例題3. どの集合にも属さない要素
**問題: 2つの集合 A, B が与えられる。どちらにも属さない要素を出力せよ。**
> [参考： ABC319 C - Elements Not in Either Set](https://atcoder.jp/contests/abc319/tasks/abc319_c)
<details><summary> 回答　</summary>

```python
N = int(input())
A = set(map(int, input().split()))
B = set(map(int, input().split()))
uncommon_elements = A ^ B  # AとBの対称差

print(*sorted(uncommon_elements))
```
</details>

### 例題4. 配列のすべての要素が異なるか判定
問題: 配列 A のすべての要素が異なる場合は YES、そうでなければ NO を出力せよ。
> [参考： ABC320 B - All Unique](https://atcoder.jp/contests/abc320/tasks/abc320_b)
<details><summary> 回答　</summary>

```python
N = int(input())
A = list(map(int, input().split()))

print("YES" if len(A) == len(set(A)) else "NO")
```
</details>

### 例題5. どのリストにも出現する要素
**問題: 3つの整数リスト A, B, C が与えられる。すべてのリストに共通する要素を出力せよ。**
> [参考： ABC322 C - Common in Three Lists](https://atcoder.jp/contests/abc322/tasks/abc322_c)
<details><summary> 回答　</summary>

```python
A = set(map(int, input().split()))
B = set(map(int, input().split()))
C = set(map(int, input().split()))

print(*sorted(A & B & C))
```
</details>