[백준/Python] 2470번 : 두 용액

문제

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

풀이

이것도 나중에 다시 풀어봐야 할 문제다.

투포인터로 풀면 쉽겠다고 생각했는데 점점 반례가 많아지면서 조건문을 덕지덕지 붙이게 됐다.

오답노트

처음 짠 코드를 보자. 

탐색 시작 지점, 탐색 종료 조건, 포인터 이동 조건 모두 잘못됐다.

1. left, right를 배열의 중간 지점(n//2)에서 시작해서 양쪽으로 옮기고 있음
   -> left, right의 탐색 시작점을 중간에서 시작하면 left, right 각각 양방향 중 어디로 포인터를 옮길지 결정해야 한다. 
   -> 내 코드에서 가장 잘못된 선택임 이것 때문에 조건문이 이상하게 많이 붙었음. 투포인터를 사용하는 목적도 장점도 모르고 쓴 결과
   -> 양쪽에서 시작하면 left는 오른쪽으로만, right는 왼쪽으로만 이동을 고려하면 됨
2. 탐색 종료 조건을 두 포인터가 교차할 때로 설정해야 함
3. 어떤 포인터를 어디로 옮길지 결정하는 로직이 잘못됨
   sum<0, sum>0이 아니라 현재까지 계산된 두 용액의 합(sum)의 절댓값의 최솟값보다 현재 가리키고 있는 두 용액의 합의 절댓값이 큰지 작은지 비교해서 포인터를 옮겨야 한다.

틀린 코드 1:

import sys
n = int(sys.stdin.readline())
liquid = list(map(int, sys.stdin.readline().split()))
liquid.sort()
left = right = n // 2
while 0<=left<n and 0<=right<n:
    sum_ = liquid[left] + liquid[right]
    if sum_ < 0:
        if right+1>=n:
            break
        else:
            right+=1
    elif sum_ > 0:
        if left-1<0:
            break
        else:
            left-=1
print(liquid[left], liquid[right])

 

그리고 다시 투포인터의 탐색 시작점을 양쪽으로 바꿔서 풀었는데 한 번 더 틀렸다.

 

틀린 코드2 :

# 특성값을 오름차순 정렬
# 두 포인터가 가리키는 특성값의 합 = sum
# abs(sum)이 이전보다 작으면 절대값을 업데이트하고 왼쪽 포인터를 오른쪽으로 or 오른쪽 포인터를 왼쪽으로 한 칸 이동
# 포인터 왼쪽 or 오른쪽 이동 기준? sum<0 이면 왼쪽 포인터를 오른쪽으로 한 칸, sum>0 이면 오른쪽 포인터를 왼 쪽으로 한 칸
# 언제까지 반복? 특성값의 합의 절대값이 0이 되면 탐색 종료
import sys
n = int(sys.stdin.readline())
liq = list(map(int, sys.stdin.readline().split()))
liq.sort()
left = 0
right = n-1
ans1 = ans2 = 0
while 0<=left<n and 0<=right<n and left<right:
    sum = liq[left] + liq[right]
    min_sum = sys.maxsize
    if abs(sum)<min_sum: # 두 용액 합의 절댓값이 더 작은 경우를 발견함
        min_sum = abs(sum) # min_sum과 ans1, ans2를 업데이트 해주기
        ans1 = left
        ans2 = right
    if sum<0:
        left += 1
    elif sum>0:
        right -= 1
    else:
        break
print(min(liq[ans1], liq[ans2]), max(liq[ans1], liq[ans2]))

반례 :

10
-87 -42 -40 -22 -11 23 29 78 79 98

틀린 이유 : min_sum을 while문 안에서 매번 초기화하고 있음

 

정답 코드 :

# 특성값을 오름차순 정렬
# 두 포인터가 가리키는 특성값의 합 = sum
# abs(sum)이 이전보다 작으면 절대값을 업데이트하고 왼쪽 포인터를 오른쪽으로 or 오른쪽 포인터를 왼쪽으로 한 칸 이동
# 포인터 왼쪽 or 오른쪽 이동 기준? sum<0 이면 왼쪽 포인터를 오른쪽으로 한 칸, sum>0 이면 오른쪽 포인터를 왼 쪽으로 한 칸
# 언제까지 반복? 특성값의 합의 절대값이 0이 되면 탐색 종료
import sys
n = int(sys.stdin.readline())
liq = list(map(int, sys.stdin.readline().split()))
liq.sort()
left = 0
right = n-1
ans1 = ans2 = 0
min_sum = sys.maxsize
while 0<=left<n and 0<=right<n and left<right:
    sum = liq[left] + liq[right]
    if abs(sum)<min_sum: # 두 용액 합의 절댓값이 더 작은 경우를 발견함
        min_sum = abs(sum) # min_sum과 ans1, ans2를 업데이트 해주기
        ans1 = left
        ans2 = right
    if sum<0:
        left += 1
    elif sum>0:
        right -= 1
    else:
        break
print(min(liq[ans1], liq[ans2]), max(liq[ans1], liq[ans2]))