[백준(Baekjoon)][자바(java)] 2470 : 두 용액 / 투 포인터

 

www.acmicpc.net/problem/2470

2470번: 두 용액

 

문제 풀이

 

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int a[] = new int[n], i;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (i = 0; i < n; i++)
			a[i] = Integer.parseInt(st.nextToken());
		br.close();

		Arrays.sort(a);

		int left = 0, right = n - 1;
		int x = 0, y = 0, value = Integer.MAX_VALUE;
		while (left < right) {
			int sum = a[left] + a[right], value_tmp = Math.abs(sum);
			if (value > value_tmp) {
				value = value_tmp;
				x = a[left];
				y = a[right];
				if (sum == 0) break;
			}
			if (sum < 0)	left++;
			else			right--;
		}
        
		System.out.println(x + " " + y);
	}
}

 

*  투 포인터

-  용액의 특성값들을 오름차순으로 정렬
-  left, right의 두 포인터를 이용하여 배열의 양 끝단에서부터 탐색 ( left < right 인 경우 )
-  두 포인터가 가리키는 용액값의 합( sum )의 절대값( = 용액의 특성값 )( value_tmp )이 현재 특성값( value )작을 때
   두 용액값( x, y ) 갱신. 0일 때가 가장 작음
-  두 용액값의 합( sum )이 0보다 작으면 left을 하나 더해주고, 나머지 경우 right을 하나 빼줌