[BOJ/python]2473번 세 용액

백준 2473번 세 용액 파이썬 투포인터

문제 링크 - https://www.acmicpc.net/problem/2473

2473번: 세 용액

다양한 방법으로 풀 수 있다. 2470번 두 용액 문제의 풀이를 활용했다. 다른 테크닉 없이 모든 용액을 하나씩 고정해두고 해당 용액 다음으로 등장하는 용액들만 사용하여 투 포인터를 사용해서 풀면 된다.

1. 풀이

우선 주어진 A 리스트를 오름차순으로 정렬한다. 투 포인터를 처음과 끝에서 시작하여 중간에서 만나면 탐색을 종료하는 방식을 사용한다. 이를 통해 0보다 합이 크면 큰 값을 빼주고, 0보다 합이 작으면 작은 값을 빼준다.

• 정렬된 A 리스트에 있는 용액을 하나씩 고정한다.
• 고정된 용액의 인덱스가 i라면 i+1번 인덱스부터 N-1번 구간에서 고정된 용액과의 합의 크기가 0에 가까운 두 용액을 찾는다.
• 만약 세 용액의 합의 절대값 크기가 tmp보다 작다면 sol 배열에 정답으로 갱신한다.
• 이후에 세 용액의 합이 0이라면 해당 고정 구간의 탐색을 중지한다.
• 세 용액의 합이 0보다 작다면 투 포인터 구간에서 시작값을 1 늘린다. (0에 가깝게 만들기 위해 작은 값을 뺀다.)
• 세 용액의 합이 0보다 크다면 투 포인터 구간에서 종료값을 1 줄인다. (0에 가깝게 만들기 위해 큰 값을 하나 뺀다.)

2. 코드

#세용액 two pointer
N= int(input())
A=list(map(int, input().split()))
A.sort()

tmp=float('inf')
sol=[]
for i in range(N-2):
    fix = A[i]    
    s,e = i+1, N-1
    while s!=e:
        if abs(A[s]+A[e]+fix) < tmp:
            tmp = abs(A[s]+A[e]+fix)
            sol = [ fix, A[s], A[e] ]
        
        if A[s]+A[e]+fix == 0 :
            break
          
        elif A[s]+A[e]+fix < 0 :
            s+=1
            
        else:
            e-=1

print(*sol)

N개의 주어진 용액을 모두 탐색한다. i번째 용액을 고정시킨 경우 N-i개의 용액에 대하여 투 포인터를 사용한다. 즉 시간복잡도는 O(N*(N-i)) = O(N^2)

새로운 풀이

좀 더 시간을 줄일 수 있는 코드를 찾아야할 것 같다.