백준 2470 - 두 용액

문제

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

 

일반화 시켜보면 주어진 리스트에서 합이 0에 가장 가까운 임의의 두 수를 찾는 문제입니다.

 

첫 풀이에서 모든 가능한 두 숫자의 조합을 대상으로 그 합을 확인하는 브루트 포스(Brute Force) 방식으로 접근했다가

시간 초과로 실패하였습니다.

 

그 후 리스트를 정렬한 뒤 투포인터 방법으로 접근하여 문제를 해결했습니다.

 

문제 풀이

각 포인터는 정렬된 리스트의 앞과 끝에서 출발하며

합이 0보다 작을 경우 앞에 위치한 포인터를 한 칸 뒤로

합이 0보다 큰 경우 뒤에 위치한 포인터를 한 칸 앞으로 옮기며

두 포인터가 같아지거나 교차할 때까지 반복합니다.

 

반복하면서 합의 절댓값이 0에 더 가까우면 정답을 갱신합니다.

예시 1

문제에 제시된 기본 예시입니다.

참고로 ph_min의 초기값은 문제 조건에 있는 "이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다" 를 고려해 설정하였습니다.

예시 2

기본 예시에선 갱신이 일어나지 않아 설명에 적합한 예시를 임의로 만들었습니다.

소스 코드

def solution(info):
    info.sort()

    ph_min = 2000000000

    idx_front = 0
    idx_end = len(info)-1
    best = [idx_front, idx_end]

    while idx_front < idx_end:
        ph_now = info[idx_front] + info[idx_end]

        if abs(ph_now) < ph_min:
            ph_min = abs(ph_now)
            best = [info[idx_front], info[idx_end]]

        if ph_now == 0:
            best = [info[idx_front], info[idx_end]]
            break

        elif ph_now > 0: idx_end -= 1
        else: idx_front += 1

    return best


N = int(input())
info = list(map(int, input().split()))

result = solution(info)
print(f'{result[0]} {result[1]}')