[백준]2470 - 두 용액 문제 풀이(파이썬,Python)

문제

2470번: 두 용액

들어가며

이분 탐색으로 접근할려고 했는데, 아무리 생각이 안나서 투포인터로 풀었다.

코드

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

arr.sort()

pl = 0
pr = n-1

result_nums = []
best_sum = 10000000000

# 끝점 두 개가 음수
if arr[pl] <= 0 and arr[pr] <= 0:
    print(f"{arr[pr-1]} {arr[pr]}")
# 끝점 두 개가 양수
elif arr[pl] > 0 and arr[pr] > 0 :
    print(f"{arr[pl]} {arr[pl+1]}")
# 끝점 두 개가 서로 혼합
else :
    while pl < pr:
        num_sum = arr[pl] + arr[pr]

        # 현재 합이 더 작다면 갱신
        if abs(num_sum) < abs(best_sum):
            best_sum = num_sum
            result = (arr[pl], arr[pr])

        # 합이 음수면 왼쪽 포인터 이동 (더 큰 값 선택)
        if num_sum < 0:
            pl += 1
        # 합이 양수면 오른쪽 포인터 이동 (더 작은 값 선택)
        elif num_sum > 0:
            pr -= 1
        # 합이 정확히 0이라면 최적이므로 종료
        else:
            break
    print(f"{result[0]} {result[1]}")

풀이

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

arr.sort()

pl = 0
pr = n-1

result_nums = []
best_sum = 10000000000

초기 입력 및 셋팅 부분이다.

arr은 입력받은 수열이다.

쉬운 탐색을 위해 정렬을 한다.

pl은 왼쪽으로 시작하는 포인터이고, pr은 오른쪽에서 시작하는 포인터이다.

result_nums는 문제에서 요구하는 합이 제일 0에 가까운 숫자이다.

best_sum은 최소값을 찾기 위해 임의의로 큰 값을 넣어두었다.

 

# 끝점 두 개가 음수
if arr[pl] <= 0 and arr[pr] <= 0:
    print(f"{arr[pr-1]} {arr[pr]}")
# 끝점 두 개가 양수
elif arr[pl] > 0 and arr[pr] > 0 :
    print(f"{arr[pl]} {arr[pl+1]}")

시간을 단축하기 위해 두 경우의 수를 앞에서 제거한다.

그게 바로 끝점 두 개가 음수인 경우와 양수인 경우이다.

음수일 땐, 정렬했을 때 맨 뒤에 두 값이 0에 제일 가까운 값이다.

양수일 땐, 정렬했을 경우 맨 앞 두 값이 0에 제일 가까운 값이다.

 

else :
    while pl < pr:
        num_sum = arr[pl] + arr[pr]

        # 현재 합이 더 작다면 갱신
        if abs(num_sum) < abs(best_sum):
            best_sum = num_sum
            result = (arr[pl], arr[pr])

        # 합이 음수면 왼쪽 포인터 이동 (더 큰 값 선택)
        if num_sum < 0:
            pl += 1
        # 합이 양수면 오른쪽 포인터 이동 (더 작은 값 선택)
        elif num_sum > 0:
            pr -= 1
        # 합이 정확히 0이라면 최적이므로 종료
        else:
            break
    print(f"{result[0]} {result[1]}")

두 경우의 수 앞에서 쳐냈기 때문에, 맨 왼쪽 값과 오른쪽값은 음수, 양수일 것이다.

여기서 투 포인터 방식을 사용하여 진행한다.

pl은 맨 왼쪽 값을 가리키고 있다.

pr은 맨 오른쪽 값을 가리키고 있다.

 

먼저, 두 포인터가 가리키고 있는 값들을 합친다. 그게 num_sum이다.

그리고 num_sum과 best_sum을 비교한다. 

현재 합이 더 작다면 이를 갱신한다.

 

이때, 합이 음수면 왼쪽 포인터를 오른쪽으로 이동한다.

왼쪽 포인터가 지나치게 작은 값을 갖고 있다는 뜻으로 더 큰 값을 선택해야 한다.

합이 양수일 땐, 반대로 진행한다.

합이 0이라면 바로 종료한다.

 

그러면 자연스럽게 result엔 최적의 경우만 들어가게 된다.