[백준] 2467번: 용액

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

initial

So we want to find a pair with the closest sum to 0. But we cannot blindly shift our left and right pointers inwards without certain conditions.

Let's see
-100 -99 98 100 1000

So my initial thinking was initialise an external variable of abs(lst[0] + lst[-1]) and if the absolute value of sum of left and right pointers is smaller than this external variable, that means we are close to the value 0 so we update the external variable with the absolute value of sum and store the value at left and right pointers. We should update that external variable with the absolute sum, not just sum so i made a careless mistake there.

solution

correct:

import sys
input = sys.stdin.readline

n=int(input())
lst = list(map(int,input().split()))
left,right = 0, len(lst)-1
start = abs(lst[left]+lst[right])
ans = [lst[left],lst[right]]
while left<right:
    sum= lst[left]+lst[right]
    if sum==0:
        print(lst[left],lst[right])
        exit()

    if abs(sum)<start:
        start=abs(sum)
        ans=[lst[left],lst[right]]

    if sum>0:
        right-=1
    else:
        left+=1
print(*ans)

this is more concise with same logic. There is no need to initialise external value with using values of lst. Just a really high arbitrary number will do.

value = 2000000000
N = int(input())
x, y = 0, 0
l = 0
r = N - 1

dragon_liquid = [int(x) for x in input().split()]
# 문제에서 이미 오름차순으로 정렬

while l < r:
    cur_value = dragon_liquid[l] + dragon_liquid[r]

    if abs(cur_value) <= value:
        x = dragon_liquid[l]
        y = dragon_liquid[r]
        value = abs(cur_value)

    if cur_value <= 0:
        l += 1

    else: # cur_value > 0
        r -= 1

print(x, y)

complexity

The code you provided is an implementation of a two-pointer approach to find two elements in an array that sum to zero with the minimum absolute value. The time complexity of this code is O(n), where 'n' is the length of the input list lst.

Here's a breakdown of the complexity:

1. Initialization: The code initializes variables left and right to 0 and len(lst)-1, which are O(1) operations.

2. Loop: The code enters a while loop that continues until left is less than right, where 'left' and 'right' are the two pointers. The loop iterates at most n/2 times, so the loop itself has O(n) complexity.

3. Sum Calculation and Comparison: Inside the loop, you calculate the sum of the elements at the 'left' and 'right' positions, and compare it to zero and the current minimum absolute sum. These operations are O(1) each.

4. Updating Pointers: Depending on the value of the sum, you increment or decrement the 'left' or 'right' pointer. These operations are O(1) as well.

Overall, the time complexity of this code is dominated by the loop, making it O(n). It efficiently finds the two elements that sum to zero with the minimum absolute value in the input list lst.