[BOJ-3273] 두 수의 합 문제를 두 가지 방식으로 풀어보자 (해시, 투 포인터) 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. 투 포인터로 해결하기
투 포인터라는 방식이 있다. 하나의 배열 위에 두개의 포인터가 움직이며 해답을 찾는 방식이다.
해당 문제의 경우 배열을 정렬한다면, 투포인터를 이용하여 쉽게 문제를 풀 수 있다.
정렬된 배열을 기준으로, 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에서 찾아보자
Stage 1
count = 0
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| value | 1 | 2 | 3 | 4 | 5 |
| start | end |
두 수의 합은 6이다.
5보다 크므로, end를 줄여준다.
Stage 2
count = 0
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| value | 1 | 2 | 3 | 4 | 5 |
| start | end |
이제 두 수의 합은 5이다.
합이 target과 일치하므로 count를 증가시켜준다.
서로 다른 값을 가진 배열이므로, 두 포인터를 모두 이동시킨다. start는 1로, end는 2으로 이동한다.
Stage 3
count = 1
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| value | 1 | 2 | 3 | 4 | 5 |
| start | end |
포인터를 옮겨도 두 수의 합은 5이다.
target과 일치하므로 count를 증가시켜준다.
서로 옮겼을 때 start는 2, end는 1로 이동한다.
이제 start가 end보다 커지므로 종료한다.
시간 복잡도
해당 로직의 시간 복잡도는 투포인터에서는 O(n)이지만 정렬에서 O(n*Log(n))의 시간이 걸리므로 최종적으로 O(n*Log(n))이 된다.
최종 코드
최종 코드는 다음과 같다.
package main
import (
"bufio"
"fmt"
"log"
"os"
"sort"
)
// https://www.acmicpc.net/problem/3273 - 두 수의 합
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 |
Stage 1
count = 0
배열
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| value | 5 | 1 | 3 | 2 | 4 |
i |
해시맵
| 현재 값 | |
|---|---|
| idx |
먼저 i에 맞는 value가 5이다. 보수 값인 0에 해당하는 값이 해시맵에 있는지 확인한다.
없으므로, 카운트는 그대로 두고 현재 값을 해시맵에 추가한다.
Stage 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인 것이 존재하지 않으므로 카운트는 그대로 두고 현재 값을 해시맵에 추가한다.
Stage 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인 것이 존재하지 않으므로 카운트는 그대로 두고 현재 값을 해시맵에 추가한다.
Stage 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인 것이 존재하므로 카운트를 증가시킨다.
이후 해시맵에 현재 값을 추가한다.
Stage 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 - 두 수의 합
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)
}
}마무리
해시와 투 포인터를 이용하여 문제를 해결할 수 있었다.
비슷한 유형의 문제를 코딩 테스트에서 풀게 되어 복기겸 정리해보았다.
필자는 바보같게도 1번 방식으로 풀었다.🤣
(오랜만에 알고리즘 문제를 풀어보니 감이 떨어져서 그런지, 너무 단순하게 생각했다.)
이후 BinarySearch를 사용하는 방식으로 풀었다가 실패했었는데, 끝나고 좀 더 생각해보니 좋은 방법을 찾을 수 있었다.
(왜 항상 시험을 칠 때는 이런 방법을 생각하지 못하는지 모르겠다. ㅠㅠ)
이런 유형의 문제를 평소에 많이 풀고, 생각날 때 이렇게 정리해두어야 시험을 칠 때에도 도움이 될 것 같다
아자아자 파이팅!