알고리즘 - Python / 백준 - 2467번 : 용액

2467번: 용액 (acmicpc.net)

2467번: 용액

 

---

풀이

• 오름차순으로 나열된 수들을 더해서 0이 되는 2개의 수를 구하는 문제다.
• 입력 자체가 오름차순으로 나열되어 있다는 점에서 힌트를 얻었다.
• 투 포인터를 사용해 좌측 , 우측에서 부터 수를 더해가면서 MIN 값과 비교한다.
• 만약 더한 값의 절댓값이 MIN보다 작으면 업데이트한다.
• 더한 값이 양수라면 0에 가까워지기 위해 양수 부분을 줄여야 하므로 뒤쪽 포인터를 앞으로 하나 민다.
• 더한값이 음수라면 0에 가까워지기 위해 음수 부분이 커져야 하므로 앞쪽 포인터를 뒤로 하나 민다.
• MIN이 0 이거나 두 포인터가 만나면 반복문을 종료하고 해당 케이스를 출력한다.

 

import sys
n = int(sys.stdin.readline())
c = list(map(int , sys.stdin.readline().split(" ")))
fp = 0; ep = len(c)-1; mins = (10**10) + 1
check_x , check_y = 0,0
while True:
    if mins == 0 or fp == ep:
        break
    if abs(mins) > abs(c[fp] + c[ep]):
        check_x = fp
        check_y = ep
        mins = c[fp] + c[ep]
    if c[fp] + c[ep] > 0:
        ep -= 1
    elif c[fp] + c[ep] < 0:
        fp += 1
print(c[check_x] ,end=" ")
print(c[check_y])

---