[백준/Python] 3273번: 두 수의 합

문제

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

3273번: 두 수의 합

---

문제 요약

n개의 서로 다른 양의 정수로 이루어진 수열에서 서로 다른 두 수의 합이 x인 쌍의 수를 출력한다.

---

코드

n = int(input())

arr = sorted(list(map(int, input().split()))) # 배열 정렬

x = int(input())

left = 0
right = n - 1

cnt = 0

while left < right:
    if arr[left] + arr[right] > x: # x 보다 크면 큰 값인 right를 1 감소
        right -= 1
    elif arr[left] + arr[right] < x: # x 보다 작으면 작은 값인 left를 1 증가
        left += 1
    else: # x와 크기가 같다면
        print(left, right)
        cnt += 1 # 정답 개수 1 증가

        # 다른 쌍이 있는지 탐색하기 위해 투포인터 변경
        left += 1 
        right -= 1

print(cnt)

---

코드 설명

1. 투 포인터를 이용하여 정렬된 배열의 맨 왼쪽과 오른쪽부터 하나씩 x와 비교하며 포인터를 움직인다.

 

2. x보다 투 포인터가 가리키는 값의 합이 크면 right 포인터를 1 감소시킨다.

 

3. x보다 투 포인터가 가리키는 값의 합이 작으면 left 포인터를 1 증가시킨다.

 

4. x와 투 포인터가 가리키는 값의 합이 같으면 정답 개수 cnt를 1 증가시키고, 다른 쌍이 있는지 탐색하기 위해 투 포인터를 한 칸씩 이동시킨다.

 

5. left포인터가 right포인터를 앞질러가면 반복을 종료한다.