[백준] 2467번 용액 - 파이썬(Python)

문제 (링크)

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

2467번: 용액

 

나의 풀이

이 문제는 투포인터와 이진탐색을 모두 사용할 수 있다.

1) 투포인터 사용

import sys
input = sys.stdin.readline

n = int(input())
liquids = list(map(int, input().split()))

left_idx = 0
right_idx = n - 1

ans = abs(liquids[left_idx] + liquids[right_idx])
ans_left = left_idx
ans_right = right_idx

while left_idx < right_idx: # left_idx와 right_idx는 만나면 안된다
    tmp = liquids[left_idx] + liquids[right_idx]

    if abs(tmp) < ans:
        ans_left = left_idx
        ans_right = right_idx
        ans = abs(tmp)

        if ans == 0:
            break
    
    if tmp < 0:
        left_idx += 1
    
    else:
        right_idx -= 1

print(liquids[ans_left], liquids[ans_right])

코드 설명 및 풀이법

투포인터 알고리즘을 사용하기 위해서 생각해야할 것은 딱 두가지이다.

 

두 개의 포인터를 각각 무엇으로 잡을지와, 각 포인터가 움직여야할 상황을 정의하는 것이다.

 

테스트케이스에서 확인할 수 있듯이 용액 중 특성값이 가장 작은 값과 큰 값을 더하는 것이 0에 가까운 특성값을 만드는 하나의 방법처럼 보인다.

 

따라서, 특성값이 가장 작은 0번 인덱스 값과 특성값이 가장 큰 마지막 값을 초기 포인터로 설정해주었다.

 

이후, 두 포인터가 가르키는 값을 더한 후 해당 값의 절대값이 0과 가장 가까운 것을 각각 저장해준다.

 

포인터를 이동시킬때는 두 포인터가 가르키는 값을 더한 값이 0보다 크냐 작냐를 기준으로 한다.

 

만약 해당 값이 0보다 작다는 것은 두 포인터가 더한 값을 증가시켜줘야하기 때문에 왼쪽 포인터를 1 더해주었고, 그게 아니라면 값을 감소시켜줘야하기 때문에 오른쪽 포인터에서 1을 빼주었다.

 

2) 이진탐색

import sys
input = sys.stdin.readline

n = int(input())
liquids = list(map(int, input().split()))

ans = float("INF")
ans_left = 0
ans_right = 0

for i in range(n-1):
    current = liquids[i]

    start = i + 1
    end = n - 1

    while start <= end:
        mid = (start + end) // 2
        tmp = current + liquids[mid]

        if abs(tmp) < ans:
            ans = abs(tmp)
            ans_left = i
            ans_right = mid

            if tmp == 0:
                break
        
        if tmp < 0:
            start = mid + 1
        
        else:
            end = mid - 1

print(liquids[ans_left], liquids[ans_right])

코드 설명 및 풀이법

용액의 i번째 값과 i+1 ~ n까지의 값의 합을 각각 이진탐색으로 구해서 0과 가장 가까운 쌍을 찾는 방식이다.

 

start와 end를 증감시키는 로직은 투포인터와 크게 다르지 않다.