[백준/python] 2467번: 용액

문제

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

2467번: 용액

---

문제 요약

크기가 N인 1차원 배열을 입력 받고 합이 0과 가장 가까운 두 수를 출력한다.

+ 오름차순으로 배열을 입력 받고 두수를 출력한다.

---

코드

N = int(input())

arr = list(map(int, input().split()))

left, right = 0, N - 1
# arr[left]과 arr[right]을 가리키는 투 포인터 
minVal = abs(arr[left] + arr[right])
ans = [arr[left], arr[right]]


while left != right: 
# 두 포인터가 만나면 종료
    if minVal > abs(arr[left] + arr[right]):
        minVal = abs(arr[left] + arr[right])
        ans = [arr[left], arr[right]]

    # 0에 더 가까운 값을 찾아야 한다.
    if arr[left] + arr[right] >= 0: # 합이 양수라면 값을 줄여야하므로
        right -= 1 # 오른쪽에 있는 큰 수를 바로 왼쪽에 있는 조금 더 작은 수로 변경
    elif arr[left] + arr[right] < 0: # 합이 음수라면
        left += 1 # 왼쪽에 있는 작은 수를 바로 오른쪽에 있는 조금 더 큰 수로 변경

print(*ans)

---

코드 설명

1. 투 포인터 left, right를 설정한다. (초기 값은 인덱스 0과 인덱스 N - 1을 가리킨다.)

 

2. 가장 0에 가까운 합을 저장하는 변수 minVal을 설정한다. (초기 값은 초기 left와 right의 합이다.

 

3. 이전 minVal보다 현재 투 포인터의 합이 더 작으면 minVal값 과 ans(minVal의 인덱스를 저장한 배열)을 갱신한다.

 

4. 현재 합이 양수라면 값을 줄여야 하므로 오른쪽 포인터를 왼쪽으로 한 칸 옮긴다.

 

5. 현재 합이 음수라면 값을 늘여야 하므로 왼쪽 포인터를 오른쪽으로 한 칸 옮긴다.

 

6. 투 포인터가 서로 만나면 반복문을 종료한다.