백준 3273번: 두수의 합 (Python)

접근

먼저 투포인터 알고리즘에 대해 알아보았다.

위 문제를 가장 직관적인 방법으로 푸는 방법은 2중 for문을 순환하면서 두 수의 합이 원하는 값을 표시할때마다 카운트해주는 것이다. 하지만 이 경우 시간복잡도가 O(n^2) 이기 때문에 리스트의 데이터가 커지면 시간 초과가 발생할 확률이 높다.

이런 경우 투포인터 알고리즘을 이용할 수 있다. 투포인터 알고리즘은 다음과 같은 방식으로 작동한다.

1. 리스트를 오름차순으로 정렬한다.
2. left는 리스트의 왼쪽 끝, right는 리스트의 오른쪽 끝을 초기값으로 가진다.
3. list[left] + list[right] 값이 원하는 수 x 보다 클 경우 right 값을 1 줄여준다.
4. list[left] + list[right] 값이 원하는 수 x 보다 작을 경우 left 값을 1 올려준다.
5. list[left] + list[right] 값이 원하는 수 x 와 일치할 경우 right 값을 1 줄여주고, left 값을 1 올려준다.
6. left와 right 값이 만날 때까지 연산을 반복해준다.

투포인터 알고리즘의 장점은 리스트를 한번만 순환해서 시간 복잡도가 훨씬 작다는 점이다. 리스트가 정렬되어 있을 경우 O(n), 정렬되어 있지 않을 경우에도 O(n logn) 의 시간 복잡도를 가져, 2중 for문보다 훨씬 빠르게 원하는 값을 찾을 수 있다.

이를 코드로 구현하면 아래와 같다.

코드

import sys

n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
x = int(sys.stdin.readline())

nums.sort()
left, right = 0, n - 1
cnt = 0
while left < right:
    tmp = nums[left] + nums[right]
    if tmp > x:
        right -= 1
    elif tmp < x:
        left += 1
    else:
        cnt += 1
        left += 1
        right -= 1
print(cnt)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!