[BOJ-3273] 2つの数の合計問題を2つの方法で解決しよう (ハッシュ法, 2ポインタ) With Go
問題
n個の異なる正の整数 a1, a2, ..., an からなる数列がある。 aiの値は1以上、1000000以下の自然数である。
自然数 x が与えられたとき、 ai + aj = x (1 ≤ i < j ≤ n) を満たす (ai, aj) の組み合わせの数を求めるプログラムを書け。上記のように与えられた配列の中で、合計が指定された数 x になるかを問う問題である。
便宜上、以下では
xをtargetと呼ぶ。
1. 二重ループで解決する
この問題を初めて受け取ったとき、単純に考えれば配列を二回回して探せると思った。
核心のロジックを抜き出すと、以下のようになる。
package main
import "fmt"
func main() {
// ... 初期化コード
count := 0
for i, num := range arr {
for j, num2 := range arr {
if i >= j {
continue
}
if num+num2 == target {
count++
}
}
}
fmt.Println(count)
}ループを二回回して、単純に探す方法である。
しかし、与えられた n の制約条件が 1 ≤ n ≤ 100000 であるため、以下のような方法を使用すると最悪の場合 O(n^2) が発生する。
最大の入力が来た場合、100,000 * 100,000 = 10,000,000,000 を比較しなければならない。
当然ながら、このコードを入れて実際に回してみると時間超過が発生する。
もっと速くて効率的な解答を考えなければならない。
2. 2ポインタで解決する
2ポインタという方法がある。1つの配列上に2つのポインタが動きながら解を探す方法である。
この問題の場合、配列をソートすれば、2ポインタを使って簡単に問題を解決できる。
ソートされた配列を基準に、start は 0 から、end は n-1 から始める。
次のような入力が入っていると仮定しよう。
arr = [5, 1, 3, 2, 4]
target = 5これをソートすると次のような形になるだろう。
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| value | 1 | 2 | 3 | 4 | 5 |
今、start は 0、end は 4 で探してみよう。
ステージ1
count = 0
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| value | 1 | 2 | 3 | 4 | 5 |
| start | end |
2つの数の合計は6である。
5より大きいため、endを減らす。
ステージ2
count = 0
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| value | 1 | 2 | 3 | 4 | 5 |
| start | end |
今、2つの数の合計は5である。
合計がtargetと一致するため、countを増加させる。
異なる値を持つ配列であるため、2つのポインタを両方移動させる。 start は 1 に、end は 2 に移動する。
ステージ3
count = 1
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| value | 1 | 2 | 3 | 4 | 5 |
| start | end |
ポインタを移動しても2つの数の合計は5である。
target と一致するため、 count を増加させる。
互いに移動した際に start は 2、 end は 1 に移動する。
今、start が end より大きくなるため、終了する。
時間計算量
このロジックの時間計算量は2ポインタでは O(n) であるが、ソートで O(n*Log(n)) の時間がかかるため、最終的には O(n*Log(n)) となる。
最終コード
最終コードは以下のようになる。
package main
import (
"bufio"
"fmt"
"log"
"os"
"sort"
)
// https://www.acmicpc.net/problem/3273 - 2つの数の合計
func main() {
writer := bufio.NewWriter(os.Stdout)
reader := bufio.NewReader(os.Stdin)
defer writer.Flush()
var n int
if _, err := fmt.Fscanln(reader, &n); err != nil {
log.Fatal(err)
}
arr := make([]int, n)
for i := 0; i < n; i++ {
if _, err := fmt.Fscan(reader, &arr[i]); err != nil {
log.Fatal(err)
}
}
if _, err := fmt.Fscanln(reader); err != nil {
log.Fatal(err)
}
var target int
if _, err := fmt.Fscanln(reader, &target); err != nil {
log.Fatal(err)
}
sort.Ints(arr)
count := 0
start, end := 0, len(arr)-1
for start < end {
sum := arr[start] + arr[end]
if sum == target {
count++
start++
end--
}
if sum > target {
end--
}
if sum < target {
start++
}
}
fmt.Println(count)
}3. ハッシュで実装する
ハッシュを利用してもこの問題を解決することができる。
補数とハッシュマップを利用すればよい。
例えば4の10の補数は、10 - 4 = 6になる。
次のように以前と同じ配列を持っていると仮定して、そのロジックを見てみよう。
ハッシュを使えばソートは必要なく、ループも一度だけ回せばよい。
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| value | 1 | 2 | 3 | 4 | 5 |
ステージ1
count = 0
配列
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| value | 5 | 1 | 3 | 2 | 4 |
i |
ハッシュマップ
| 現在の値 | |
|---|---|
| idx |
まず、i に対応する value が5である。補数値の0に対応する値がハッシュマップにあるか確認する。
ないので、カウントはそのままにして、現在の値をハッシュマップに追加する。
ステージ2
count = 0
配列
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| value | 5 | 1 | 3 | 2 | 4 |
i |
ハッシュマップ
| 現在の値 | 5 |
|---|---|
| idx | 0 |
次に、i=1値は1である。1に対する補数である4をハッシュマップで探す。
ハッシュマップにキー値が4のものは存在しないため、カウントはそのままにして、現在の値をハッシュマップに追加する。
ステージ3
count = 0
配列
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| value | 5 | 1 | 3 | 2 | 4 |
i |
ハッシュマップ
| 現在の値 | 5 | 1 | |:—-:|:-:| | idx | 0 | 1 |
次に、i=2 値は3である。3に対する補数である2をハッシュマップで探す。
ハッシュマップにキー値が2のものは存在しないため、カウントはそのままにして、現在の値をハッシュマップに追加する。
ステージ4
count = 0
配列
| index | 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|---|
| value | 5 | 1 | 3 | 2 | 4 | |
i |
ハッシュマップ
| 現在の値 | 5 | 1 | 3 |
|---|---|---|---|
| idx | 0 | 1 | 2 |
次に、i=3 値は2である。2に対する補数である3をハッシュマップで探す。
ハッシュマップにキー値が3のものは存在するため、カウントを増やす。その後、ハッシュマップに現在の値を追加する。
ステージ5
count = 1
配列
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| value | 5 | 1 | 3 | 2 | 4 |
i |
ハッシュマップ
| 現在の値 | 5 | 1 | 3 | 2 |
|---|---|---|---|---|
| idx | 0 | 1 | 2 | 3 |
次に、i=4 値は4である。4に対する補数である1をハッシュマップで探す。
ハッシュマップにキー値が1のものは存在するため、カウントを増やす。その後、ハッシュマップに追加する。
結果
count = 2
配列
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| value | 5 | 1 | 3 | 2 | 4 |
ハッシュマップ
| 現在の値 | 5 | 1 | 3 | 2 | 4 |
|---|---|---|---|---|---|
| idx | 0 | 1 | 2 | 3 | 4 |
i は5となり終了し、アルゴリズムの結果の配列とハッシュマップは上記の通りである。
countは最終的に2になる。
時間計算量
ハッシュを利用した場合、別途ソートをする過程がなく、ループも一度だけ実行されるため O(n) の時間計算量を持つ。
ただし、マップの特性上、メモリ使用量は入力に応じて大きくなる副作用があるかもしれない。（もちろん、ハッシュマップの実装方法により空間計算量は異なる）
最終コード
これをGoコードに移すと以下のように実装できる。
package main
import (
"bufio"
"fmt"
"log"
"os"
)
// https://www.acmicpc.net/problem/3273 - 2つの数の合計
func main() {
writer := bufio.NewWriter(os.Stdout)
reader := bufio.NewReader(os.Stdin)
defer writer.Flush()
var n int
if _, err := fmt.Fscanln(reader, &n); err != nil {
log.Fatal(err)
}
arr := make([]int, n)
for i := 0; i < n; i++ {
if _, err := fmt.Fscan(reader, &arr[i]); err != nil {
log.Fatal(err)
}
}
if _, err := fmt.Fscanln(reader); err != nil {
log.Fatal(err)
}
var target int
if _, err := fmt.Fscanln(reader, &target); err != nil {
log.Fatal(err)
}
count := 0
idxMap := make(map[int]int)
for i, num := range arr {
// numの補数を探す
if _, ok := idxMap[target-num]; ok {
count++
}
// ハッシュマップに現在の値を追加
idxMap[num] = i
}
if _, err := fmt.Fprintln(writer, count); err != nil {
log.Fatal(err)
}
}終わりに
ハッシュと2ポインタを利用して問題を解決することができた。
似たようなタイプの問題をコーディングテストで解くことになり、振り返りながら整理してみた。
私は無知にも1番の方法で解いた。🤣
（久しぶりにアルゴリズムの問題を解いてみて、感が鈍ったのか、あまり単純に考えすぎた。）
その後、バイナリサーチを用いる方法で解こうとして失敗したが、終わってみると、もっと良い方法を見つけることができた。
（なぜいつも試験の時になるとこんな方法を考えられないのか分からない。 ㅠㅠ）
このような種類の問題を普段からたくさん解いて、思いついたときにこのように整理しておくと、試験の際にも役立つと思われる。
あざあざファイティング！