백준 2473 : 세 용액 (Python)

본문 링크

import sys
input=sys.stdin.readline

N=int(input())

L=sorted(list(map(int,input().split())))

count=3000000000 ; answer=[]
for i in range(N-2):
    start=i+1 ; end=N-1
    while start<end:
        if L[i]+L[start]+L[end]==0:
            print(L[i] , L[start] , L[end])
            exit(0)
        elif abs(L[i]+L[start]+L[end])<count:
            answer=[ L[i] , L[start] , L[end] ]
            count=abs(L[i]+L[start]+L[end])
        if L[i]+L[start]+L[end]>0:
            end-=1
        else:
            start+=1
print(*answer)

📌 어떻게 접근할 것인가?

어떤 리스트를 주어졌을때 세수의 합이 0 에 가장 가까운 것을 찾는 문제이다.

두 용액이나 용액 문제를 풀었다면 이 문제는 투 포인터를 사용하여 풀 수 있다는 것을 알것이다.
하지만 세 수의 합은 어떻게 구할까?

문제 조건에서 보면 $N$은 3 이상 5,000 이하의 정수이다.
반복문으로 리스트 한 값을 잡고 투 포인터를 돌려서 총 세수의 합을 구하면 어떨까?

$N$은 10만이상이 아니라 고작 5000이하이기 때문에 가능하다.
따라서 투포인터 와 완전탐색을 섞은 형태의 코드를 작성했다.

📌어떻게 투 포인터를 사용할 것인가?

리스트의 길이에서 -2 를 한 만큼 반복문을 돌려준다.
start 는 반복문의 인덱스 + 1로 잡고 end=n-1 로 잡는다.

L[i] 값과 투 포인터의 값이 count 보다 작은지 판별해준다.
세 수의 합의 절대값이 count 변수보다 작으면 그 세 값을 담아주고 count 변수도 세 수의 합으로 변경해준다.

그리고 세 수의 합이 0 보다 크면 end 를 감소시켜 값을 줄이고 0 보다 작으면 start 값을 증가시켜서
0 에 가장 가깝게 탐색하도록 한다.

✅ 코드에서 주의해야할 부분

• count=3000000000으로 잡는다
• 리스트는 꼭 정렬해준다.
• abs(L[i]+L[start]+L[end])값이 count보다 클때의 조건은 필요없으므로 넣지않는다. 시간초과가 발생할수있다.
• pypy로 제출해야지 통과가능하다.