[Baekjoon] # 2470: 두 용액

두 용액

문제

산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 

알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때,

이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 

두 용액을 찾는 프로그램을 작성하시오.

예제

• 입력

첫째 줄에는 전체 용액의 수 N이 입력된다.

N은 2 이상 100,000 이하이다.

둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다.

이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다.

N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

5
-2 4 -99 -1 98

• 출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다.

출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다.

특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

-99 98

---

Solution

def get_inputs():
    import sys

    input_data = sys.stdin.read()
    inputs = input_data.splitlines()

    item_count = int(inputs[0])
    data = list(map(int, inputs[1].split(" ")))

    return item_count, data


def solution(item_count, data):
    # 주어진 배열 오름차순으로 정렬
    data.sort()

    left, right = 0, item_count - 1

    # 최솟값 저장
    closest_distance = float("inf")
    answer = None

    while left < right:
        sum = data[left] + data[right]

        # `sum`이 `target = 0`과 같으면 return
        if sum == 0:
            return str(data[left]) + " " + str(data[right])

        distance = abs(sum)

        # `target`과 가장 가까운 값인 경우, 최솟값 갱신
        if closest_distance > distance:
            answer = [data[left], data[right]]
            closest_distance = distance

        # 배열이 정렬이 되어 있으므로
        # `sum`이 `target`보다 큰 경우, 더 작은 수의 포인터
        if sum > 0:
            right -= 1
        # `sum`이 `target`보다 작은 경우, 더 큰 수의 포인터
        else:
            left += 1

    return str(answer[0]) + " " + str(answer[1])


def main():
    item_count, data = get_inputs()

    result = solution(item_count, data)
    print(result)


if __name__ == "__main__":
    main()

---

해결 방법

---

Two Pointer

위 문제는 두 개의 포인터를 사용해서 배열을 탐색해가는 Two Pointer 패턴으로 해결할 수 있다.

Two Pointer는 아래와 같은 문제를 해결할 때 사용한다.

1. 정렬된 배열에서 두 수의 합이 target과 같거나 가까운 쌍 찾기
2. 배열에서 중복된 원소 제거하기
3. 회문(Palindrome) 확인하기

---

해결 과정

아래 3 가지 과정을 통해서 target과 가장 가까운 값을 찾을 수 있다.

1. 정렬 및 초기화
   • 주어진 배열을 오름차순으로 정렬
   • 배열의 양 끝에 두 포인터(left, right) 위치
   • closest_distance와 answer 변수 초기화
2. 합 계산 및 비교
   • 두 포인터가 가리키는 값의 합 계산: sum = arr[left] + arr[right]
   • 합이 target과 같으면 즉시 해당 값 반환
   • 다르다면 distance = abs(sum - target)을 계산하여 closest_distance와 비교 후 필요시 answer 갱신
3. 포인터 이동
   • sum > target: 오른쪽 포인터를 왼쪽으로 이동 (right -= 1)
   • sum < target: 왼쪽 포인터를 오른쪽으로 이동 (left += 1)
   • left < right일 때까지 2번 과정부터 반복

배열이 정렬되어 있기 때문에,

합이 목표값보다 크면 더 작은 값을, 작으면 더 큰 값을 선택하며 target에 가까워질 수 있다.

---

의사 코드

Function solution(item_count, array):
    // 배열을 오름차순으로 정렬
    Sort array

    // 양쪽 끝에서 시작하는 두 포인터 초기화
    left = 0
    right = item_count - 1
    
    // 가장 가까운 거리와 정답을 저장할 변수 초기화
    closest_distance = 무한대
    answer = null

    // 두 포인터가 교차할 때까지 반복
    While left < right:
        // 현재 두 수의 합 계산
        sum = array[left] + array[right]

        // 합이 0이면 즉시 해당 두 수를 문자열로 반환
        If sum equals 0:
            Return array[left]와 array[right]를 문자열로 변환하여 공백으로 연결

        // 현재 합의 절대값(0과의 거리) 계산
        distance = |sum|

        // 이전까지의 최소 거리보다 현재 거리가 더 작으면 정답 업데이트
        If closest_distance > distance:
            answer = [array[left], array[right]]
            closest_distance = distance

        // 합이 양수면 오른쪽 포인터를 왼쪽으로 이동
        If sum > 0:
            right = right - 1
        // 합이 음수면 왼쪽 포인터를 오른쪽으로 이동
        Else:
            left = left + 1

    // 최종적으로 찾은 두 수를 문자열로 변환하여 반환
    Return answer[0]와 answer[1]을 문자열로 변환하여 공백으로 연결

---

URL

• 두 용액