[백준] 2470 : 두 용액

문제

막힌 부분

이진탐색을 도대체 어디서 써줘야 할 지를 모르겠다.
그냥 그 자!체!를 모르겠다!!!!!!!
용액 특성값 리스트에서 2개씩 골라서 합을 구한 다음, 그 합을 가지고 이진탐색을 해줘야 하는지..? 잘 모르겠다.

나눠줘야 하는 경우의 수

공유기 설치 문제는 left, right, mid 값이 인덱스가 아니라 공유기를 설치할 마을 사이의 거리였는데,
이 문제는 left, right, mid 값이 리스트의 인덱스이다!

1) 두 용액의 특성값의 합이 0인 경우
while문을 break하고 결과 출력

2) 두 용액의 특성값의 합이 음수인 경우
음의 특성값이 양의 특성값의 절댓값보다 크기 때문에 left += 1을 통해 두 용액의 특성값이 합이 0에 가까워지도록 함

3) 두 용액의 특성값의 합이 양수인 경우
양의 특성값이 음의 특성값의 절댓값보다 크기 때문에 right -= 1을 통해 두 용액의 특성값의 합이 0에 가까워지도록 함

최소인 값을 구할 수 있는 left, right 인덱스 값을 구하기 위한 업데이트 부분

특성값이 0에 가장 가까운 용액을 만들어내야 하므로 절댓값이 작아야 함

만약 두 용액의 특성값의 합의 절댓값이 기존의 answer의 절댓값보다 작은 경우 answer에 새로운 값 입력
+)
두 변수에 각각 left, right 인덱스 값 저장

(절댓값 쓰는 경우: -2, 1 있을 때 절댓값 안쓰면 -2가 min으로 출력되기 때문에 절댓값을 이용해줘야)

https://data-bank.tistory.com/29

구조

• 리스트에 용액들의 특성값을 입력합니다.
• 리스트를 오름차순으로 정렬합니다.
• left = 0, right = N - 1로 설정하고 이분탐색을 위해 left < right 일 때까지 while문을 반복합니다.
  (left < right인 이유 : 두 용액은 모두 다르기 때문에)

i ) 두 용액의 특성값의 합이 0인 경우

• while문을 break하고 결과를 출력합니다.

ii) 두 용액의 특성값의 합이 음수인 경우

• 음의 특성값의 절댓값이 양의 특성값의 절댓값보다 크기 때문에 left += 1 을 통해 두 용액의 특성값의 합이 0에 가까워 질 수 있도록 합니다.

iii) 두 용액의 특성값의 합이 양수인 경우

• 양의 특성값의 절댓값이 음의 특성값의 절댓값보다 크기 때문에 right -= 1를 통해 두 용액의 특성값의 합이 0에 가까워질 수 있도록 합니다.

• 만약 두 용액의 특성값의 합의 절댓값이 기존의 answer의 절댓값보다 작은 경우 answer 에 새로운 값을 입력하고 al =left, ar = right 을 통해 index를 저장해 줍니다. min을 사용하게 되면 -2와 1을 비교했을 때 answer 에 -2 가 입력되고 이는 오답이기 때문에 절댓값을 활용합니다.

출처
https://data-bank.tistory.com/29

22.04.12 다시 풀어보기

import sys

N = int(sys.stdin.readline())
W = sorted(list(map(int, sys.stdin.readline().split()))) # 오름차순으로 정렬

start = 0
end = N - 1
minValue = W[0] + W[N-1]
x = start
y = end

while start < end:
    sum = W[start] + W[end]
    
    if sum == 0:
        x = start
        y = end
        break
    
    if abs(minValue) > abs(sum):
        x = start
        y = end
        minValue = sum
   
    if sum > 0:
        end -= 1
    elif sum < 0:
        start += 1
    
print(W[x], W[y])

다른 사람 풀이

import sys

n = int(sys.stdin.readline())
w = list(map(int, sys.stdin.readline().split()))

w.sort()
left = 0
right = n - 1
answer = w[left] + w[right] # 처음에는 가장 작은 수와 가장 큰 수를 더한 합을 answer로 넣어둠
al = left
ar = right

while left < right:
    tmp = w[left] + w[right] # "현재 left와 right의 합"인 tmp와 기존의 최솟값인 answer를 비교해서 최솟값을 계속 갱신해주는 것
    if abs(tmp) < abs(answer): # 기존 answer보다 "현재 left와 right의 합"인 tmp 가 작을 때 최솟값을 갱신
        answer = tmp # 현재 합인 tmp를 answer에 넣어줌
        al = left
        ar = right
        if answer == 0: # 만약 합이 0이 되면 break 해줌
            break
    
    if tmp < 0:
        left += 1 # 합이 음수이면 음수의 절댓값이 양수의 절댓값보다 큰 것이기 때문에 left += 1
    else:
        right -= 1 # 합이 양수이면 양수의 절댓값이 음수의 절댓값보다 큰 것이기 때문에 right -= 1
    
print(w[al], w[ar])
        

나의 풀이!

left < right으로만 이분탐색을 진행해줘야 한다!!
left = right인 케이스가 포함되면 안되는 이유는 용액이 모두 서로 다르기 때문이다.

처음에 left <= right으로 해줘서..... 계속 96%에서 틀렸습니다! 라고 떴음 ㅜ

다른 사람 풀이를 보면 알겠지만, 나는 알칼리성, 산성이 모두 둘 다 여러 개 있을 경우에만 이분탐색을 진행했는데, 그럴 필요 없이 모든 케이스에 대해 이분탐색을 진행해주면 모두 잘 뜬다.
정렬이 다 잘 되어 있다면 이분탐색이 당연히 될테니까!

import sys
n = int(sys.stdin.readline())
w = list(map(int, sys.stdin.readline().split()))
w = sorted(w)
a = [] # 알칼리성 음의 정수
s = [] # 산성 양의 정수

al = 0 # left 인덱스
ar = 0 # right 인덱스

# 알칼리성과 산성을 분류
for i in w:
    if i < 0:
        a.append(i)
    elif i > 0:
        s.append(i)
a = sorted(a)
s = sorted(s)

if len(s) == 0 and len(a) > 0: # 음수인 것만 있을 때
    print(a[-2], a[-1])
elif len(a) == 0 and len(s) > 0: # 양수인 것만 있을 때
    print(s[0], s[1])
else: # 음수와 양수의 조합
    # 음수가 한 개이고 양수가 여러개
    if len(a) == 1 and len(s) > 1:
        al = 0
        ar = 1
        p = 0
        tmp = s[0] + s[1] # 양수인 것 두 개의 합
        for i in range(len(s)):
            if tmp > abs(a[0] + s[i]): # 음수 한 개와 양수 여러개들의 합이 양수 작은 것 두개의 합보다 작으면 업데이트
                tmp = abs(a[0] + s[i])
                al = 0
                ar = i
                p = 1
        # 프린트
        if p == 1:
            print(a[0], s[ar])
        elif p == 0:
            print(s[0], s[1])
        
    # 양수가 한 개이고 음수가 여러개
    elif len(s) == 1 and len(a) > 1:
        al = -2
        ar = -1
        p = 0
        tmp = abs(a[-2] + a[-1]) # 음수인 것 두 개의 합
        for i in range(len(a)):
            if tmp > abs(s[0] + a[i]): # 양수 한 개와 음수 여러개들의 합이 음수 작은 것 두개의 절댓값의 합보다 작으면 업데이트
                tmp = abs(s[0] + a[i])
                al = 0
                ar = i
                p = 1
        # 프린트
        if p == 1:
            print(a[ar], s[0])
        elif p == 0:
            print(a[-2], a[-1])
    
    elif len(s) == 1 and len(a) == 1:
        print(a[0], s[0])
    
    # 둘 다 여러 개
    else:
        left = 0
        right = len(w) - 1
        
        al = 0
        ar = 0
        tmp = float('inf')
        
        while left < right: # 용액은 모두 서로 다르기 때문에 left = right으로 인덱스가 같은 케이스는 포함시켜주면 안 됨!
            if tmp > abs(w[left] + w[right]):
                al = left
                ar = right
                tmp = abs(w[left] + w[right])
            
            if w[left] + w[right] == 0:
                al = left
                ar = right
                break
            elif w[left] + w[right] < 0:
                left += 1
            
            else:
                right -= 1
            
        print(w[al], w[ar])               

22.05.10

다시 풀어보면서 막혔던 부분에서 또 막혔다.
이 문제는 일반적인 이진탐색 문제와 약간 결이 다른데, 보통 구하라는 것 자체를 기준으로 start와 end를 만드는데 이 문제는 다르다.
구하라는 것이 바로 특성값이 0에 가장 가까운 용액을 만드는 것이었다. 그러나 start와 end를 특성값을 기준으로 두고 하면 어렵다. 여기서 start와 end는 정렬되어 있는 용액 리스트에서 인덱스를 의미한다.
그리고 두 인덱스의 값의 합이 음수이면 음수의 영향력을 줄여줘야 하므로 start += 1을 해주고, 양수이면 양수의 영향력을 줄여줘야 하므로 end -= 1을 해준다. 따라서 mid는 따로 필요 없다.
마지막으로, while 조건 또한 독특한데, 으레 하는 while start <= end가 아닌, while start < end를 해준다는 것이다. while start < end를 해주는 이유는 두 용액이 반드시 달라야 하기 때문이다. <=를 쓰면 동일한 용액을 두 번 쓰는 것이므로 문제의 조건에 맞지 않다.

import sys
input = sys.stdin.readline

n = int(input())
water = sorted(list(map(int, input().split())))

def bsearch():
    start = 0
    end = n-1
    first = 0
    second = 0
    minhap = float('inf') # 처음에 999999로 놓고 풀었다가 32%에서 틀림 ㅜㅜㅜ
    while start < end:
        hap = water[start] + water[end]
        if minhap >= abs(hap):
            minhap = abs(hap)
            first = water[start]
            second = water[end]
        if hap < 0:
            start += 1
        elif hap > 0:
            end -= 1
        else: # hap == 0
            first = water[start]
            second = water[end]
            break
    print(first, second)


bsearch()