[백준] 2473_세 용액 (투 포인터 이용)

📕 문제

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

2473번: 세 용액

 

💡 풀이법

1. 이 문제는 포인터가 총 세개이기 때문에 한 포인터는 고정시키고 두 포인터를 욺직여야 한다.

2. 투포인터를 이용하려면 먼저 리스트가 오름차순 정렬이 되어있어야 한다.

3. 가장 앞의 포인터를 for문을 돌면서 먼저 i로 지정해주고, left 포인터는 i+1, right 포인터는 N-1로 해준다.

4. 세 값들의 합이 0보다 크면 right를 -1 해주고, 0보다 작으면 left를 +1 해준다.

5. total(세 숫자의 합의 절대값)이 answer_sum(0과 가장 가까운 합을 담는 변수)보다 작다면 answer(세개의 값이 담길 리스트)를 변화시켜주고, answer_sum을 total로 변화시켜준다.

6. 만약 total이 0이라면 flag를 True로 바꿔주고 return 한다.

( flag는 함수 밖의 for문도 바로 빠져나가기 위해 만들어준 break)

 

def two_pointer(lst, start, end):
    global mark, answer_sum, flag
    left, right = start, end

    while left < right:
        total = mark + lst[left] + lst[right]

        if abs(total) < answer_sum:
            answer[0] = mark
            answer[1] = lst[left]
            answer[2] = lst[right]
            answer_sum = abs(total)
                
            if total == 0:
                flag = True
                return
        
        if total > 0:
            right -= 1
        elif total < 0:
            left += 1
    
    
N = int(input())
nums = list(map(int,input().split()))
nums.sort()
answer_sum = float('inf')
answer = [0]*3
flag = False
for i in range(N-2):
    mark = nums[i]
    two_pointer(nums, i+1, N-1)
    if flag:
        break
print(*answer)