Hanbit the Developer
[Python] 백준 2473번: 세 용액 본문
https://www.acmicpc.net/problem/2473
import sys
input = sys.stdin.readline
INF = 3000000000
def getMinAbsFluids():
minAbsSum = INF
minAbsFluids = [0, 0, 0]
for i in range(N-2):
left, right = i + 1, N - 1
while left < right:
curSum = fluids[i] + fluids[left] + fluids[right]
curAbsSum = abs(curSum)
# minAbs 갱신
if curAbsSum < minAbsSum:
minAbsSum = curAbsSum
minAbsFluids = [fluids[i], fluids[left], fluids[right]]
# 0에 수렴하게끔 인덱스 조정
if curSum > 0:
right -= 1
elif curSum < 0:
left += 1
else:
return minAbsFluids
return minAbsFluids
if __name__ == '__main__':
N = int(input())
fluids = list(map(int, input().split()))
fluids.sort()
minAbsFluids = getMinAbsFluids()
print(*minAbsFluids)
3SUM 알고리즘을 이용했다.
우선 메인 함수를 호출하기에 앞서, 오름차순으로 정렬시켜야한다.
먼저 while문 안의 로직에 대해 언급하자면, 해당 로직은 left와 right을, 합이 0에 수렴하게끔 유도하여 줄여나가면서, 최소절대값(minAbsSum)과 그 때의 용액의 특성값들(minAbsFluids)을 갱신시킨다.
해당 while문을 i를 증가시키면서 0...N-3까지 진행하며, left는 i+1, right는 N-1로 초기화시킨다.
i=0일 때, 다음과 같이 진행된다.
그리고 INF를 2999999998으로 설정해야한다. 왜냐하면 특성값이 중복될 수 없으며, 1000000000이 특성값의 최대값이기 때문이다.
시간복잡도는 O(N^2)이다.
'Algorithm > 백준' 카테고리의 다른 글
[Python] 백준 9328번: 열쇠 (0) | 2021.07.11 |
---|---|
[Python] 백준 2623번: 음악프로그램 (0) | 2021.07.09 |
[Python] 백준 2467번: 용액(시간복잡도 2등) (0) | 2021.07.07 |
[Python] 백준 2239번: 스도쿠 (0) | 2021.07.06 |
[Python] 2166번: 다각형의 면적 (0) | 2021.07.05 |