Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

26. 투 포인터

투 포인터 알고리즘과 meet in the middle 알고리즘을 배워 봅시다.

Java / Python

2. 두 용액

2470번

A[i] + A[j]가 0에 가까운 경우를 찾는 문제

이번 문제는 산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하는 문제입니다.

리스트에 용액들의 특성값을 입력하고 리스트를 오름차순으로 정렬한 후 start = 0, end = N - 1로 설정하고 이분탐색을 위해 start < end 일 때까지 while문을 반복합니다.

• 두 용액의 특성값의 합이 음수인 경우
  음의 특성값의 절댓값이 양의 특성값의 절댓값보다 크기 때문에 start += 1 을 통해 두 용액 특성값의 합이 0에 가까워지도록 합니다.
• 두 용액의 특성값의 합이 양수인 경우
  양의 특성값의 절댓값이 음의 특성값의 절댓값보다 크기 때문에 end -= 1를 통해 두 용액 특성값의 합이 0에 가까워지도록 합니다.

• Java

import java.io.*;
import java.util.*;

public class Main {  
	static int N;
	static int[] arr;
	static int point1 = -1;
	static int point2 = -1;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   
		StringTokenizer st; 
        
		N = Integer.parseInt(br.readLine());   
		arr = new int[N]; 
        
		st = new StringTokenizer(br.readLine()); 
		for(int i = 0; i < N; i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}
        
		Arrays.sort(arr);
        
		solution();
        
		bw.write(point1 + " " + point2 + "\n");
        
		bw.flush();
		br.close();
		bw.close();
	}
	static void solution(){
		int start = 0;
		int end = N - 1;
		int max = 2000000000;
        
		while(start < end) {
			int sum = arr[start] + arr[end];
 
			// 두 용액 갱신
			if(Math.abs(sum) < max) {
				point1 = arr[start];
				point2 = arr[end];
				max = Math.abs(sum);
			}
 
			if(sum > 0)
				end--;
			else
				start++;
		}       
	}
}

• Python

import sys

N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()
start, end = 0, N - 1
result = 2e+9+1
answer = [] # 정답

while start < end:
    p1 = arr[start]
    p2 = arr[end]
    tmp = p1 + p2
    if abs(tmp) < result: 
        result = abs(tmp)
        answer = [p1, p2] 
        
    if tmp < 0:
        start += 1
    else: end -= 1
        
print(answer[0], answer[1])