파이썬 | 백준 | 2473 | 세 용액

 

Solution. 투 포인터

세 특성값 중 하나를 고정으로 두고 나머지 두 값을 가지고 투포인터..

# 2473, 세 용액
import sys

N = int(sys.stdin.readline())
solution = list(map(int, sys.stdin.readline().split(" ")))

solution.sort()
diff = 3000000001  # 세 용액 특성값의 합 0에 가깝게
res = []
for i in range(len(solution) - 2):
    # 중복 체크
    if i > 0 and solution[i] == solution[i - 1]:
        continue

    left = i + 1
    right = len(solution) - 1
    while left < right:
        sum = solution[i] + solution[left] + solution[right]

        temp = abs(sum - 0)

        if temp == 0:
            print(solution[i], solution[left], solution[right])
            sys.exit()

        # 특성값이 현재 특성값보다 0에 가깝다면
        if temp < diff:
            diff = temp
            res = [solution[i], solution[left], solution[right]]
            
            # 산성이 더 더해진 경우 sum이 양수. 산성의 정도를 낮춘다.
            if sum > 0:
                right -= 1
            # 염기성이 더 더해진 경우 sum이 음수. 염기성의 정도를 낮춘다.
            else:
                left += 1
                
            # 중복 제거
            while 0 < left < right and solution[left] == solution[left - 1]:
                left += 1
            while left < right < len(solution) - 1 and solution[right] == solution[right + 1]:
                right -= 1
        # 특성값이 현재 특성값보다 0에 가깝지 않다면
        else:
            # 산성이 더 더해진 경우 sum이 양수. 산성의 정도를 낮춘다.
            if sum > 0:
                right -= 1
            # 염기성이 더 더해진 경우 sum이 음수. 염기성의 정도를 낮춘다.
            else:
                left += 1

print(*res)

 

처음에 diff의 초기값을 1000000001로 했었어서 히든케이스에서 틀렸었다.

반례: 세 용액이 염기성이든 산성이든 같은 특성을 갖고 모두 최대(최대에 가까운 값)일 경우라면 혼합된 용액의 특성값을 초기값과 비교하기 위해서는 3000000001로 초기화를 해야한다.

 

ex)

5
-999999999 -1000000000 -1000000000 -1000000000 -1000000000

 

https://li-fo.tistory.com/121

과 다른 점은 0일 때 / 0과 최대한 가까운 값일 때를 구해야 한다.

 

문제 https://www.acmicpc.net/problem/2473

2473번: 세 용액