BOJ 2470 - 두 용액 (투 포인터)

https://www.acmicpc.net/problem/2470

2470번: 두 용액

 

- 서로 다른 두 용액을 더해서 합이 최대한 0에 가깝게 만드는 문제

- 산성 용액 (1 ~ 10억)

- 알칼리성 용액 (-10억 ~ -1)

 

 

아이디어

기존의 이분탐색 풀이법을 생각해보면 먼저 용액들을 정렬을 해준 후 이분탐색을 통해 답을 구했었다. 

 

새로운 관점으로 투 포인터를 활용해서 풀이를 해보자

 

포인터 L과 R을 사용한다. L은 제일 작은 원소(최소)를 가리키고, R은 제일 큰 원소(최대)를 가리키도록 한다. 

 

• 최소와 최대를 더했을 때 0보다 작은 경우
  • 최소 용액 입장에선 최대 용액이랑 더해도 음수라는 뜻이므로 최선의 짝을 찾은 것이다. 따라서 삭제해주고 더 이상 고려하지 않는다.

 

• 최소와 최대를 더했을 때 0보다 큰 경우 
  • 최대 용액 입장에서 최소 용액이랑 더해도 양수라는 뜻이므로 최선의 짝을 찾은 것이다. 따라서 삭제해주고 더 이상 고려하지 않는다. 

 

예를 들어 용액이 -99 -2 -1 4 98인 경우를 생각해보자

• L + R < 0  
  • L이 최선책을 만났으므로 L++로 제외

 

• L + R > 0
  • R이 최선책을 만났으므로 R--로 제외

이런 과정을 반복해서 최선책을 만날때마다 0과 가까운 값으로 갱신해주기만 하면 답을 구할 수 있다.

 

시간 복잡도

1. L과 R을 빠르게 찾기 위해 정렬을 해준다. -> O(N logN)

2. 원소가 1개가 될 때까지 반복해야 한다. -> N번 반복

3. 따라서 총 O(N logN)의 시간이 걸린다. 

 

 

구현

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int[] list;

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        list = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
    }

    static void pro() throws IOException {
        // list 정렬
        Arrays.sort(list, 1, N + 1);

        // 투 포인터
        int L = 1;
        int R = N;
        int r1 = 0;
        int r2 = 0;
        int ans = Integer.MAX_VALUE;

        // L == R의 경우는 한 용액만 남는 경우임
        while (L < R) {
            int sum = list[L] + list[R];

            // ans, r1, r2 갱신
            if (Math.abs(sum) < ans) {
                // 비교하기 쉽도록 절댓값으로 갱신
                ans = Math.abs(sum);
                r1 = list[L];
                r2 = list[R];
            }

            // 최소와 최대를 더했을 때 0보다 큰 경우
            if (sum > 0) {
                R--;

            // 최소와 최대를 더했을 때 0보다 작은 경우
            } else {
                L++;
            }
        }

        bw.write(r1+" "+r2);
    }

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

        pro();

        bw.close();
    }

}