[Python] 2470. 두 용액

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

2470번: 두 용액

 

접근법

• 작은 순서대로 정렬한 후 이분 탐색을 통해 가장 0에 가까운 수를 찾음
• 현재 두 용액의 합이 기존의 최소값보다 작을 경우 더 0에 가까운 값이 있나 찾아야 함 → L += 1을 통해 합의 크기를 키움
• 현재 두 용액의 합이 기존의 최소값보다 클 경우 더 작은 합을 찾아야 함 → R -=1 을 통해 합의 크기를 줄임

import sys
def input_func(N):
    arr = list((map(int,input().split())))
    arr.sort()
    return arr


def sum_func(arr):
    L = 0
    R = len(arr) - 1
    min = [sys.maxsize, L, R] # 두 용액합의 현재까지의 최소값, L idx, R idx

    while L < R:
        sum = arr[L] + arr[R]
        if sum == 0:
            min[1], min[2] = arr[L], arr[R]
            break
        if abs(sum) < abs(min[0]):
            min[0] = sum
            min[1] = arr[L]
            min[2] = arr[R]
        if sum < 0: # 최소값이 0보다 작음, abs[0]으로 업데이트 되지 않을 수 있으므로 현재 값들의 합 이용
            L += 1
        else: # 최소값이 0보다 크기 때문에
            R -= 1
    print(min[1], min[2])
    return


def main():
    N = int(input())
    arr = input_func(N)
    sum_func(arr)

if __name__=="__main__":
    main()

---

유의할 점 및 새로 배운 사항 

1. sys.maxsize 

sys.maxsize를 통해 int형의 최대값을 알 수 있다.

 

---

처음 생각했던 알고리즘의 문제점(틀린이유)

try1

(1) 처음 min[0]값을 설정할 때 arr내 가장 큰 값을 사용하면 될 거란 생각에 min[0] = arr[R]을 활용했다.

이러니 두 값의 합이 arr[R]보다 클 경우(arr의 모든 값이 양수인 경우) min[0]의 값이 업데이트 되지 않는 경우가 존재하였다.

-> min[0]을 초기화 할 때 sys.maxsize를 활용하도록 수정했다.

 

(2) 현재 값들의 합(sum)이 아닌 현재까지 나온 두 용액의 최소값을 L, R을 움직이는 기준으로 사용

→ sum이 항상 현재까지의 나온 두 용액의 최소값보다 작을 보장이 없기 때문에 sum을 비교에 활용해야함.

 

def input_func(N):
    arr = list((map(int,input().split())))
    arr.sort()
    return arr


def sum_func(arr):
    L = 0
    R = len(arr) - 1
    min = [arr[R], L, R] # 두 용액합의 현재까지의 최소값, L idx, R idx

    while L < R:
        sum = arr[L] + arr[R]
        if sum == 0:
            min[1], min[2] = arr[L], arr[R]
            break
        if abs(sum) < abs(min[0]):
            min[0] = sum
            min[1] = arr[L]
            min[2] = arr[R]
        if min[0] < 0: # 최소값이 0보다 작음, abs[0]으로 업데이트 되지 않을 수 있으므로 현재 값들의 합 이용 필요
            L += 1
        else: # 최소값이 0보다 크기 때문에
            R -= 1
    print(min[1], min[2])
    return


def main():
    N = int(input())
    arr = input_func(N)
    sum_func(arr)

if __name__=="__main__":
    main()

사용된 알고리즘

정렬, 이분탐색, 두 포인터