[백준 BOJ] 2467: 용액 - python

SUN·2023년 4월 4일

algorithm

목록 보기

30/30

알고리즘 스터디를 운영하고 있기 때문에 매주 알고리즘 문제는 계속 풀고 있긴 하지만
회사 업무로 시간이 부족해서 블로그에 정리를 많이 못하고 있다ㅠㅠ
그런데 이 문제는 일반적인 풀이와 다르게 조금 특별한 아이디어로 풀었기 때문에 짬을 내 공유하고자 한다.

오늘 풀 문제는 용액이다.

문제

풀이과정

처음 든 생각은 뭐지? 어떻게 하지? 전혀 감이 잡히지 않았다.
그리고 힌트까지 봤다. 이분 탐색과 투포인터란다.
그래도 모르겠었다. 일단 침착하게 생각해봤다.

-99 -2 -1 4 98
이렇게 값이 있을 때
두 값을 어떻게 뽑아야 0에 가깝게 나오는 지를 생각해봤다.

내가 98이라면 우선 가장 가까운 값인 4를 봐야할 거고
가장 절댓값의 차이가 적은 -99를 봐야할 거다.

내가 -2라면 가장 가까운 값인 -1을 봐야할거고
가장 절댓값의 차이가 적은 4를 봐야할 거다.

어? 절댓값?
결국 음수든 양수든 '두 수의 거리가 가까울 때'를 더해야 0에 가까워진다는 결론을 얻었다.

그래서 음수 양수 상관없이 값의 크기대로 재배열을 해봤다.
-2 -1 4 98 -99

이러면 명확해진다.
나를 기준으로 양옆만 비교해나가면서 최솟값을 찾을 수 있다!

그럼 어떻게 이렇게 배열을 하느냐?
(절댓값, 실제값) 튜플을 원소로 가진 리스트를 만들고 이 리스트를 절댓값 기준으로 정렬한다.
그리고 실제로 연산할 때는 실제값 기준으로 연산하면 된다.

정답 코드

n = int(input())
values = [(abs(int(elem)), int(elem)) for elem in input().split()]
values.sort()

answer = []
pre = values[0][1]
min_mix_value = float("inf")
for i in range(1, n):
    abs_v, real_v = values[i]
    curr_mix_value = abs(pre + real_v)

    if curr_mix_value < min_mix_value:
        min_mix_value = curr_mix_value
        answer = [pre, real_v]

    pre = real_v

print(*sorted(answer))

이렇게 간단하게 정답을 맞출 수 있었다.
참고로 min_mix_value를 초기화할 때 1e9로 했다가 틀렸습니다떠서 로직이 틀린줄 알고 당황했는데
1e9로는 최대범위를 커버하기에 충분치 않아서였다.
최솟값 초기화할 때는 웬만하면 float('inf')로 해줘야겠다는 교훈을 얻었다.

다른 사람의 풀이

투포인터나 이분탐색 풀이가 대부분이다.

투포인터 풀이

# input 입력 받기
n = int(input())
solution = list(map(int, input().split(' ')))

# 정렬하기
solution.sort()

# 이중포인터 설정
left = 0
right = n-1

answer = 2e+9+1 # 기준값
final = [] # 정답

# 투포인터 진행
while left < right:
    s_left = solution[left]
    s_right = solution[right]

    tot = s_left + s_right
    # 두 용액의 합이 0과 가장 가까운 용액을 정답에 담아주기
    if abs(tot) < answer:
        answer = abs(tot)
        final = [s_left, s_right]
	
    # 두 용액의합이 0보다 작다면 왼쪽의 값을 늘려 조금 더 0에 가깝게 만들어준다
    if tot < 0:
        left += 1
    # 반대로, 두 용액의 합이 0보다 크다면 오른쪽의 값을 줄여서 조금 더 0에 가깝게 만들어준다
    else:
        right -= 1

print(final[0], final[1])

특성값이 가장 작은 0번 인덱스 값과 특성값이 가장 큰 마지막 값을 초기 포인터로 설정해준다.
그리고 포인터를 이동하면서 최솟값을 찾는데,
포인터를 이동시킬때는 두 포인터가 가르키는 값을 더한 값이 0보다 크냐 작냐를 기준으로 한다.

만약 두 용액의 합이 음수라면 왼쪽 포인터를 오른쪽으로 한 칸 옮기고
양수라면 오른쪽 포인터를 왼쪽으로 한칸 옮기면 된다.

왜냐하면 합이 음수일 때 이 값을 더 0에 가깝게 하려면 작은 값을 크게 해야 하고
양수라면 큰 값을 작게 해야 하기 때문이다.

이분탐색 풀이

n = int(input())
arr = sorted(map(int, input().split()))  # 정렬된 용액들


def binary_search(s, target):
    global arr
    res = n
    start, end = s, n - 1

    while start <= end:
        mid = (start + end) // 2
        if arr[mid] >= target:
            res = mid
            end = mid - 1
        else:
            start = mid + 1
    return res


def solution():
    global arr
    v1, v2 = 0, 0
    best_sum = 10 ** 10
    for i in range(n):
        # 이분 탐색 수행: 현재 위치(i) 이후의 용액에서 탐색, 찾는 값은 (현재 용액 * -1)
        res = binary_search(i + 1, -arr[i])
        
        # 찾은 용액의 왼쪽 용액 확인
        if i + 1 <= res - 1 < n and abs(arr[i] + arr[res - 1]) < best_sum:
            best_sum = abs(arr[i] + arr[res - 1])
            v1, v2 = arr[i], arr[res - 1]

        # 찾은 용액 확인
        if i + 1 <= res < n and abs(arr[i] + arr[res]) < best_sum:
            best_sum = abs(arr[i] + arr[res])
            v1, v2 = arr[i], arr[res]
    
    print(v1, v2) # i 번째 용액을 확인할 때 i + 1번 용액부터 확인하기 때문에 항상 v1 <= v2 이다.


solution()