[백준 3273 파이썬] 두 수의 합 (실버 3, 투 포인터)

알고리즘 유형 : 투 포인터
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

n = int(input())
arr = sorted(list(map(int, input().split())))
x = int(input())

# 양 끝에 포인터 두기
i = 0
j = n-1
count = 0

# 두 포인터가 교차할 때 종료
# 그 이후의 (j, i) 쌍은 이미 (i, j) 쌍에서
# 처리된 경우들임
while i < j:
    sum_tmp = arr[i] + arr[j]
    if sum_tmp == x:
        count += 1
        i += 1
        j -= 1
    elif sum_tmp > x:
        j -= 1
    else:
        i += 1

print(count)

풀이 요약

1. 두 개의 포인터를 0과 n-1에 둔다. 이 때 배열은 반드시 정렬되어있어야 한다.

2. 포인터 쌍에 대해 합을 구하고 그 것을 x와 비교한다.

   합이 x보다 큰 경우에는 합을 줄여야하므로, 오름차순 정렬된 배열에 대해 오른쪽 포인터를 왼쪽으로 옮기면 합이 작아지므로 포인터를 옮긴다.

   합이 x보다 작은 경우에는 합을 키워야하므로, 왼쪽 포인터를 오른쪽으로 한 칸 옮겨 합을 키운다.

   합과 x가 같은 경우에는 카운팅해주고, 두 포인터를 한 칸 이동시킨다. 둘 다 이동시켜주는 이유는, 둘 중 하나만 이동시켰을 때 반드시 합이 달라지므로 어차피 x와 같지 않게된다. 그래서 둘 다 이동시켜주는 것이다. 시간복잡도 줄이기에 조금이나마 도움이 될 것이다.

배운 점, 어려웠던 점

• 투 포인터 알고리즘에 대해 배울 수 있었다.