백준 3273번 - 두 수의 합 (Go)

https://www.acmicpc.net/problem/3273

분석

이 문제는 수열이 주어지고 수열 내에서 서로 다른 자연수 2개를 더했을 때, x 가 되는 쌍을 구해야 합니다.

수열의 크기가 1 <= n <= 100,000 이기 때문에 단순하게 이중 for 문을 사용하면 100,000 ^ 2 = 10,000,000,000 이 되기 때문에

시간 초과입니다.

 

그래서 활용한 알고리즘은 투 포인터 입니다.

이 알고리즘을 사용하기 위해선 수열이 우선 정렬되어 있어야 합니다. 

두 수의 쌍을 찾으면 되기 때문에 수열의 첫 번째와 끝부터 시작하여 서로 더해가면서 포인터를 조절하며 찾으면 됩니다.

 

그리고 1 <= x <= 2000000 이기 때문에 int 형을 사용해서 풀면 됩니다.

 

시간복잡도는 배열 탐색 O(N), 수열 정렬 O(NlogN) 이므로 O(NlogN) 입니다.

공간복잡도는 최대 int 형 10만개이므로 8byte * 10만 = 80만 byte 로 0.8 MB 입니다.

풀이 코드

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n int
	fmt.Fscan(in, &n)

	nums := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &nums[i])
	}

	sort.Ints(nums)

	var x int
	fmt.Fscan(in, &x)

	left, right := 0, len(nums) - 1
	res := 0

	for left < right {
		cur := nums[left] + nums[right]

		if cur == x {
			res++
			left++
			right--
		} else if cur < x {
			left++
		} else if cur > x {
			right--
		}
	}

	fmt.Fprintln(out, res)
}

회고

기본적인 투 포인터 활용 문제였습니다.