[BOJ/Python] 2473. 세 용액

📌 문제

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

2473번: 세 용액

 

📌 문제 접근 방법

1. 움직이지 않는 기준을 하나 설정하고 왼쪽, 오른쪽 인덱스를 바꿔가면서 합을 도출한다.
   합이 양수라면 오른쪽 인덱스를 -1, 음수라면 왼쪽 인덱스를 +1 해줘서 0에 가깝게 만들어준다.
2. 위의 과정을 반복하며 합이 0과 가장 가까운 인덱스 3개를 저장한다.
3. 시간 초과 해결
   1, 2의 과정으로는 자꾸 시간 초과가 나서 다음의 시도를 해보았다.
   • 기준점(j)이 이전의 숫자와 같을 경우 : 똑같은 합이 나오므로 continue해서 제외시키기
   • answer에 인덱스가 아닌 값을 저장하기 : 매번 값을 찾느라 시간이 더 걸리나 싶어서 인덱스만 저장하는 방식으로 바꿔주었다.
   • 만약 합과 0의 차이가 이미 0이 되었다면 더 이상 반복문을 진행하지 않고 끝내기
4. 결국엔 3번째 코드를 추가해줘서 시간초과를 해결했다.

 

📌 코드

# 백준 2473 세 용액
N = int(input())
liquid = list(map(int, input().split()))
liquid.sort()

min_diff = float('inf')
answer = []

for j in range(N-2):
    if j > 0 and liquid[j] == liquid[j-1]:
        continue

    l = j + 1
    r = N - 1

    while l < r:
        total = liquid[j] + liquid[l] + liquid[r]
        diff = abs(total)

        if diff < min_diff:
            min_diff = diff
            answer = [j, l, r]
            
        if total > 0:
            r -= 1
        elif total < 0:
            l += 1
        else:
            break
    
    if not min_diff:
        break

print(liquid[answer[0]], liquid[answer[1]], liquid[answer[2]])