[백준] 2473번 세 용액 (파이썬, 두 포인터)

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

2473번: 세 용액

 

이 문제는 이전 용액 문제를 풀고 푸는 것을 추천한다.

2021.08.08 - [Coding Test/Algorithm] - [백준] 2467번 용액 (파이썬)

[백준] 2467번 용액 (파이썬)

 

오늘도 신나는 알고리즘 

 

해당 문제는 또 다시 포인터를 움직여 가며 푸는 문제로 이번엔 세개의 용액을 선택해야한다는 차이가 있었다.

여러 생각을 하며 짰다가 지웠다가를 반복하고 for문에 while문을 곁들인 코드로 마무리 했다.

 

import sys

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

result = 10000000000

index = []
for i in range(n-2):
    l = i+1
    h = n-1
    while(l < h):
        tmp = arr[i] + arr[l] + arr[h]
        if abs(result) > abs(tmp):
            result = tmp
            index = [arr[i], arr[l], arr[h]]
        if tmp > 0:
            h -= 1
        elif tmp < 0:
            l += 1
        else:
            break
print(index[0], index[1], index[2])

 

코드 자체는 심플하다.

 

전체 값이 만약 0보다 작다면 이미 arr[h]는 최대 값이기에 l에 1을 더해서 arr[l]의 값을 더 큭게하고

만약 0보다 크다면 반대로 arr[h]를 줄여서 가장 큰 값을 줄이는 방식을 사용했다.

이런식으로 i를 0부터 n-3까지 진행해주면 가장 0에 근접한 값이 무엇인지 알수 있었다.

 

파이썬3는 시간초과가 뜨지만 pypy로 하면 문제 없게 통과된다.