boj.kr/2470 두 용액 (gold5) 파이썬 풀이

1. p1, p2에 각각 0과 정수 배열의 길이-1을 저장한다.

2. ans 변수에 정수배열에서 p1, p2 인덱스의 두 값을 저장한다.

3. 정수배열의 p1, p2 인덱스의 두 값을 더한 값을 tot 변수에 저장한다.

4. tot의 절댓값을 min_tot에 저장한다.

5. p1 이 p2보다 작으면 아래 6-10을 반복한다.

6. 정수배열의 p1, p2 인덱스의 두 값을 더한 값의 절댓값이 min_tot보다 작으면 ans의 0, 1번 인덱스의 값을 정수배열의 p1, p2인덱스의 값으로 갱신한다.

7. min_tot 값을 저장한다.

8. tot 값을 저장한다.

9. tot 값이 음수이면 p1을 1 증감하고 tot 값이 양수이면 p2값을 1 감소한다.

10. tot 값이 0이면 반복문을 빠져나온다.

11. ans 배열을 정렬하고 순서대로 출력한다.

 

N = int(input())
nums = list(map(int, input().split()))
nums.sort()

p1 = 0
p2 = len(nums)-1
ans = [nums[p1], nums[p2]]
tot = nums[p1] + nums[p2]
min_tot = abs(tot)

while p1 < p2:
    tot_abs = abs(nums[p1] + nums[p2])
    if min_tot > tot_abs:
        ans[0] = nums[p1]
        ans[1] = nums[p2]
    min_tot = min(min_tot, tot_abs)
    tot = nums[p1] + nums[p2]
    if tot < 0:
        p1 += 1
    elif tot > 0:
        p2 -= 1
    else:
        break

ans.sort()
print(*ans)

 

정렬, 투포인터, 이분탐색으로 분류되는 문제이다. 정렬한 후에 투포인터를 정수배열의 왼쪽 시작인덱스와 오른쪽 끝인덱스로 주어야 한다. 왜냐하면 그렇게 해야 음수인 경우에는 왼쪽의 포인터를 1 증감하고 양수인 경우에는 오른쪽의 포인터를 1 감소함으로서 각 포인터에 해당하는 정수배열의 두 요소의 값의 합을 0에 가깝도록 순차적으로 탐색할 수 있기 때문이다.