Problem Solving/백준

[BOJ 백준] 2473번 : 세 용액(Python, 파이썬)

돌돌김 2021. 2. 20. 20:40

 

www.acmicpc.net/problem/2473

 

2473번: 세 용액

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상

www.acmicpc.net

투 포인터를 활용해서 문제를 풀었다. 기존의 투 포인터와 다른 점은 확인해야 할 값이 1개 더 있는것인데, 이것은 추가적인 포인터를 1개 더 두어 해결하였다.

 

포인터가 1개 더 추가 되면서 포인터끼리 겹치는 경우가 발생할 수 있기 때문에 따로 체크를 해줘야 한다.

 

세 용액의 합이 0이 되는 경우는 여러개 있을 수 있고, 그 중 아무거나 출력하면 되기 때문에 세 지점에서의 값들의 합이 0 이 되면 출력 후 종료했다.

 

 

소스코드

 

import sys
n = int(input())
solutionList = list(map(int, input().split()))
solutionList.sort()
global p1 # 왼쪽부터 시작 
global p2 # 오른쪽 부터 시작
global p3 # 고정 포인터
global ans_p1
global ans_p2
global ans_p3

answer = sys.maxsize
for i in range(n):
    p1, p2 = 0, n-1
    p3 = i    
    while p1 < p2:
        if p1 == p3: # 같은 용액을 2번 고르는 경우 방지
            p1 += 1
        if p2 == p3:
            p2 -=1
        if p1 == p2:
            break
        result = solutionList[p1] + solutionList[p2] + solutionList[p3]
        if abs(result) < answer: # 절대값이 작은게 0에 가까운 값
            ans_p1 = p1
            ans_p2 = p2
            ans_p3 = p3
            answer = abs(result)
        if result < 0: 
            p1 += 1
        elif result > 0:
            p2 -= 1
        else: # 세 용액의 합이 0이 된 경우. 정답  
            answer = [solutionList[ans_p1], solutionList[ans_p2], solutionList[ans_p3]]
            print(*sorted(answer))
            exit(0)    
answer = [solutionList[ans_p1],solutionList[ans_p2],solutionList[ans_p3]]
print(*sorted(answer))
1 2 3 4 5 6 7 ··· 64