[백준] 1253 파이썬

문제

---

• 백준 1253 (골드 4)

백준 1253

N개의 수 중에서 다른 수 두 개의 합으로 나타낼 수 있는 수의 개수를 찾는 문제였다.
얼마 전에 풀어봤던 문제여서 쉽게 다시 풀 수 있었다.

투포인터 알고리즘

---

• 배열이나 리스트에서 ‘두 개의 포인터’를 사용하여 ‘특정 조건을 만족하는 부분 구간’을 효율적으로 탐색하는 알고리즘
• 보통은 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킴
• 탐색 범위 내에서 특정 조건을 만족하는 요소를 찾거나, 조건을 만족하는 부분 배열의 길이 등을 계산하는 데 사용
• 투 포인터의 수행 단계
  1. 배열 또는 리스트의 시작 위치에 첫 번째 포인터와 두 번째 포인터를 설정
  2. 두 포인터 사이의 구간을 조사하고 조건을 확인
  3. 조건을 만족할 경우, 원하는 결과를 얻었으므로 알고리즘을 종료
  4. 조건을 만족하지 않을 경우, 첫 번째 또는 두 번째 포인터를 이동
  5. 다시 2번 단계로 돌아가 반복
• 파이썬 예시 코드는 아래와 같다.

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))
ans = sys.maxsize
left, right = 0, n - 1

arr.sort()
x, y = 0, n - 1

while x < y:
    mix = arr[x] + arr[y]
    if abs(mix) < ans:
        ans = abs(mix)
        left = x
        right = y

    if mix > 0:
        y -= 1
    elif mix < 0:
        x += 1
    else:
        break

print(arr[left], arr[right])

내 코드

---

투포인터를 활용하여서 풀 수 있었다.
정렬 후에 처음과 마지막 값을 더해서 타겟보다 작다면 왼쪽 포인터를 이동하고, 타겟보다 크다면 오른쪽 포인터를 이동한다.
이동하는 과정에서 타겟과 같다면 정답을 하나씩 올리는 방식으로 구현하였다.

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))
ans = 0

a.sort()
left, right = 0, n-1
sum = a[0] + a[n-1]

for i in range(n):
    if i == 0:
        left, right = 1, n-1
    elif i == n-1:
        left, right = 0, n-2
    else:
        left, right = 0, n-1

    while left < right:
        sum = a[left] + a[right]
        if a[i] < sum:
            right -= 1
            if right == i:
                right -= 1
        elif a[i] > sum:
            left += 1
            if left == i:
                left += 1
        else:
            ans += 1
            break

if n == 1:
    print(0)
else:
    print(ans)