[백준3273번] 두 수의 합 / Python3

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

예제 입력 1

9
5 12 7 10 9 1 2 3 11
13

예제 출력 1

3

나의 풀이

해당 문제의 풀이는 이진탐색을 사용하는 방법과 투 포인터 기법을 사용하는 두 가지의 방법이 존재합니다.

첫번째로 이진탐색을 사용하는 방법을 설명드리겠습니다. 우선, 이진탐색을 사용하기 위해 주어지는 수열을 오름차순으로 정렬을 해줍니다. 그리고 왼쪽에서부터 모든 원소를 방문하면서 x - 원소의 값을 배열에서 이진탐색을 사용해 찾아보고 있으면 카운트를 1증가시키는 방식으로 해결할 수 있습니다. 여기서 한가지 주목할 점은 문제에서 주어지는 수열은 서로 다른 n개의 정수로 이루어져있다고 쓰여있습니다. 앞선 방법에서 수열의 모든 원소를 방문하며 x - 원소의 값을 찾았는데 만약, x가 4이고 현재 방문한 원소가 2라면? 2가 수열에 존재하므로 카운팅이 되게 됩니다. 따라서 원소 * 2가 x가 되는 경우에는 이진탐색을 진행하면 안됩니다. 이제 모든 원소를 방문하고 카운트가 세어졌다면 정답은 count // 2가 됩니다. 왜냐하면, x가 13일때 1 + 12와 12 + 1과 같이 같은 원소이지만 순서가 다른 경우도 카운팅이 되기때문입니다.

이진 탐색을 사용하는 경우, 처음 정렬할 때 O(NlogN)의 시간복잡도를 가지고 모든 원소를 탐색하면서 이진탐색을 하므로 이 경우에도 O(NlogN)의 시간복잡도를 가지므로 총 소요되는 시간복잡도는 O(NlogN)이 됩니다.

두번째로는 투 포인터 기법을 사용하는 방법에 대하여 설명드리겠습니다. 투 포인터 기법이란, 말 그래로 두 개의 포인터로 배열을 가르키며 확인해나가는 방법으로 이 문제에서는 하나의 포인터는 가장 왼쪽에서부터 또 다른 하나의 포인터는 가장 오른쪽에서부터 움직이기 시작합니다. 또한, 이 경우에도 두 포인터가 가르키는 값을 더해보고 x보다 큰지 작은지를 비교하여 왼쪽과 오른쪽 포인터를 움직이므로 주어지는 수열을 오름차순으로 정렬하는 과정이 필요합니다. 아래는 투 포인터 기법으로 답을 찾는 과정을 그림으로 나타낸 것입니다.

가장 왼쪽을 i, 오른쪽을 j로 두고 시작하며, seq[i] + seq[j]가 x와 같다면 카운터를 증가시키고 i를 왼쪽으로 한 칸 움직입니다. 그럼 seq[1] + seq[8] = 14로 x보다 크기때문에 i를 오른쪽으로 움직이면 더한 값은 항상 x보다 커지기 때문에 j를 더 작은 숫자쪽인 왼쪽으로 움직여야 합니다. 이런식으로 두 개의 포인터를 계속 이동시키며 i >= j가 되는 순간부터는 포인터가 엇갈려지는 순간으로 반복을 중지하게 됩니다.

투 포인터 기법을 사용하는 경우, 처음 정렬할때 O(NlogN), 포인터가 움직이는 총 횟수 O(N)으로 총 시간복잡도는 O(NlogN)이 됩니다.

코드

# 3273번 두 수의 합 (binary_search)


def binary_search(start, end, key):
    if start > end:
        return 0

    mid = (start + end) // 2

    if seq[mid] == key:
        return 1
    elif seq[mid] > key:
        return binary_search(start, mid - 1, key)
    elif seq[mid] < key:
        return binary_search(mid + 1, end, key)


n = int(input())
seq = list(map(int, input().split()))
x = int(input())
answer = 0

seq.sort()

for num in seq:
    if (num * 2) == x:
        continue
    answer += binary_search(0, len(seq) - 1, x - num)

print(answer // 2)

# 3273번 두 수의 합 (two pointer)

n = int(input())
seq = list(map(int, input().split()))
x = int(input())
answer = 0

seq.sort()

i = 0
j = len(seq) - 1
while i != j:
    if seq[i] + seq[j] == x:
        answer += 1
        i += 1
    elif seq[i] + seq[j] > x:
        j -= 1
    else:
        i += 1

print(answer)