백준 2470 두 용액

백준 2470 두 용액

 

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

2470번: 두 용액

 

 

배열 정렬후, 각 끝 인덱스 값 합과 target과 비교.

만약 합이 target보다 작으면 left + 1 이동

합이 target보다 크면 right -1 이동

 

 

 

📄 나의 풀이1

# 배열의 index를 left, right로 하고
# 가깝지 않으면 index 이동하는 방식으로 풀어야 하나..?
# 두 용액의 합이 0에 가까운지 비교
import sys
input = sys.stdin.readline

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

# N = 5
# solutions = [-2, 4, -99, -1, 98]

solutions.sort() # [-99, -2, -1, 4, 98]

left = 0
right = N-1
target = 0
min_diff = float('inf')
result = [0]*2

while(left < right):
    cur_sum = solutions[left] + solutions[right]
    diff = abs(cur_sum - target)

    if diff == 0:
        result[0] = solutions[left]
        result[1] = solutions[right]
        break

    if diff < min_diff:
        min_diff = diff
        result[0] = solutions[left]
        result[1] = solutions[right]

    # 범위 조정할 때는 음수, 양수 여부가 중요함!
    if cur_sum < min_diff:
        left += 1
    else:
        right -= 1

print(*result)

 

📄 나의 풀이2

import sys

N = int(sys.stdin.readline().rstrip())

solutions = list(map(int, sys.stdin.readline().rstrip().split()))

target = 0
result = [0]*2
s = sorted(solutions)

def binary_search(s, target, result):
    min_diff = float("inf")

    for idx in range(len(s)-1):
        pl = idx+1 # 가장 작은 인덱스
        pr = len(s) -1 # 가장 큰 인덱스

        while pl <= pr:
            mid_idx = (pl + pr) // 2

            if s[idx] + s[mid_idx] == target:
                result[0] = s[idx]
                result[1] = s[mid_idx]
                return result
            
            diff = abs(0 - (s[idx] + s[mid_idx])) 
            if diff < min_diff:
                min_diff = diff
                result[0] = s[idx]
                result[1] = s[mid_idx]

            if s[idx] + s[mid_idx] < target:
                pl = mid_idx + 1
            else:
                pr = mid_idx - 1

    return result


print(*binary_search(s, target, result))