[PS] BOJ2470 두 용액 ( Two Pointer ) with JAVA

 

2470번: 두 용액

 

 

◎ 문제풀이 

 

여러 용액 중 2가지를 골라 합칠 때, 그 값이 0에 가장 가까운 조합을 고르는 문제이다. 가장 간단한 풀이는 2가지 조합을 구하는 문제이니 2중 for문을 만들어서 완전탐색하는 것이다. 그러나 용액이 최대 100,000개이니 2중 for문으로 탐색하면 시간제한에 걸릴 수 있다. 

 

여기서는 TwoPointer 알고리즘을 활용하는 것이 좋다.

 

Two Pointer 알고리즘은 정렬과 두개의 포인터를 이용하여 시간복잡도를 줄일 수 있다. 그럼 입력받은 용액을 오름차순으로 정렬해보자. 

 

 

 

 

 

LEFT와 RIGHT는 양끝에서 시작한다. 

LEFT와 RIGHT가 가라키는 두 용액을 합친다. 두 용액을 합치면 50이 된다.

0에 가장 가까운 수를 구하는 문제이니 절대값도 구한다. 

 

여기서 Two Pointer의 위력이 나온다. 

 

두 용액을 합쳤을 때 양수가 나오면 LEFT를 이동해봤자 의미가 없다. 

 

( 100 , -50 ) => 50

( 100 , -20) => 80

( 100 , -5 ) => 95

.

.

.

 

LEFT를 이동하니 합이 점점 증가한다. 이중for문으로 탐색했다면 위 조합도 모두 탐색했을 것이다. 만약 양수가 나올 때, LEFT는 가만히 있고 RIGHT만 이동한다면 위 조합을 고려하지 않을 수 있다. 시간복잡도가 줄어드는 것이다.

 

 

 

 

 

이전의 두 용액의 합이 양수이니 RIGHT를 이동했다. 

절대값이 14이다.

50보다 0에 가까우니 0과 가장 가까운 조합은 (-50,64)가 된다.

 

 

 

 

 

이전의 두 용액의 합이 양수이니 RIGHT를 이동했다.

절대값이 13이다.

14보다 0에 가까우니 0과 가장 가까운 조합은 (-50,37)이 된다.

 

그런데 이번에는 두 용액의 합이 음수가 나왔다. 

두 용액의 합이 음수이면 RIGHT를 이동해보았자, 절대값만 점점 커질뿐이다. 그러므로 음수가 나오면 LEFT를 이동한다.

 

 

 

 

이전의 두 용액의 합이 음수이니 LEFT를 이동했다.

절대값이 17이다.

13보다 0에 가깝지 않으니 0과 가장 가까운 조합은 그대로 (-50,37)이 된다.

 

이 과정을 RIGHT와 LEFT가 만날때 까지 반복하면 된다. Two Pointer 알고리즘은 정렬과 두가지 Pointer를 활용하여, 조건에 따라 두 가지 포인터의 이동을 달리하면 의미없는 탐색을 획기적으로 줄일 수 있다. 

 

 

◎코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

import static java.lang.Math.*;

//BOJ2470 두 용액
public class Main {
    static StringTokenizer st;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        input();
        solution();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        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); // 오름차순 정렬
    }

    public static void solution(){
        int leftP = 0;
        int rightP = arr.length-1;

        int ansLeft = 0;
        int ansRight = 0;
        int pivot = Integer.MAX_VALUE;

        while( leftP < rightP ) {
            int sum = arr[rightP] + arr[leftP]; // 두용액 합치기

            if(pivot > abs(sum)){ // 절대값 비교
                pivot = abs(sum);
                ansLeft = arr[leftP]; //0에 가장 가까운 조합 저장
                ansRight = arr[rightP];
            }

            if(sum>0) rightP--; // 합이 양수인 경우, RIGHT 이동
            else leftP++; // 합이 음수인 경우, LEFT 이동
        }

        System.out.println(ansLeft + " "+ ansRight);
    }

}