BOJ/백준-2470-python

문제

풀이

• 산성은 양수이며, 알칼리성은 음수이다.
• 두 용액을 혼합하여 0에 가까운 용액을 만들려고 한다.
• 용액이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하라 (시간 제한 1초).
• 처음에는 음수면 알칼리 리스트로, 양수면 산성 리스트로 두 개의 리스트로 입력값을 분할한 뒤, 반복문으로 쌍을 만들어내 가장 작은값을 제출하였으나 시간 초과로 실패하였다.
• 시간안에 풀기 위해선,
  -> 하나의 리스트 요소에 순차적으로 접근(분할 x)
  -> 2중 반복문(x)
  -> 요소 두 개의 위치를 기록하면서 반복(반복문을 효율적으로 사용)
• 투 포인터 알고리즘을 사용해 문제를 접근했다.
  

코드

# boj, 2470: 두 용액, python3
import sys

def solve(n, l):
    left, right = 0, n-1
    x, y = left, right
    num1 = l[left] + l[right]

    while left < right:
        num2 = l[left] + l[right]

        if abs(num2) < abs(num1):
            num1 = num2
            x, y = left, right

            if num1 == 0:
                break

        if num2 < 0:
            left += 1
        else:
            right -= 1

    return l[x], l[y]

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    solution = sorted(map(int, sys.stdin.readline().split()))

    print(*solve(n, solution))

결과

출처 && 깃허브

boj
github