P.2467 용액

코드

package Baekjoon.Class;

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

public class P_2467 {

    static int[] arr;
    static int ansP1, ansP2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int p1 = 0, p2 = n - 1;
        ansP1 = p1; ansP2 = p2;

        twoPoint(p1, p2);
        bw.write(arr[ansP1] + " " + arr[ansP2]);
        bw.flush();

        bw.close();
        br.close();
    }

    private static int twoPoint(int p1, int p2) {
        int ans = 2000000000;

        while (p1 < p2) {
            int mix = arr[p1] + arr[p2];

            if (Math.abs(mix) < ans) {
                ans = Math.abs(mix);
                ansP1 = p1;
                ansP2 = p2;
            }

            if (mix < 0) p1++;
            else p2--;
        }

        return ans;
    }
}

코드 설명

초기 아이디어는 산성 용액, 알칼리성 용액을 따로 저장하여 조건에 따라 한칸씩 증가하며 비교하려했다.

이 아이디어에 착안하여 투포인터를 생각하게 되었고 따로 배열을 두지 않고 입력받은 배열만을 이용해 답을 구할 수 있게 되었다.

이미 입력 배열이 오름차순으로 정렬되어있기 때문에 추가적으로 정렬이 필요하지 않고 양 끝에 두 점을 두면 바로 알고리즘을 사용할 수 있게 된다.

 

두 개의 포인터의 위치가 변하는 조건은 혼합물이 양수이냐 음수이냐이다.

초기에 왼쪽에 존재하는 포인터를 p1,  오른쪽에 존재하는 포인터를 p2라고 했을 때 혼합물이 양수가 나올 경우 두 포인터가 가리키고 있는 용액의 절댓값이 p2가 더 크다는 말이 된다.

따라서 혼합물이 양수일 경우 p2를 한 칸씩 앞으로 당긴다.

 

혼합물이 음수가 나올 경우 두 포인터가 가리키고 있는 용액의 절댓값이 p1이 더 크게 된다.

따라서 혼합물이 음수일 경우 p1를 한 칸씩 뒤로 민다.

 

문제에서는 용액이 알칼리, 산성 중 한 가지만 존재할 수 있다고 하였는데 이 조건은 위와 같은 알고리즘을 채택하면 신경 쓰지 않아도 된다.

용액이 모두 음수라고 가정해보자.

-4 -3 -2 -1

이 때 p1은 -4를, p2는 -1을 가리키는데 용액의 합이 0과 가깝기 위해서는 p2는 무조건 -1을 가리켜야 한다.

위의 알고리즘에 따라서도 p1만 계속 뒤로 밀리며 (-4, -1), (-3, -1), (-2, -1) 순으로 비교를 하므로 답이 도출되게 된다.

 

용액이 모두 양수라고 가정해보자.

1 2 3 4

이 때 p1은 1을,  p2는 4를 가리키는데 용액의 합이 0과 가깝기 위해서는 p1이 무조건 1을 가리켜야 한다.

위의 알고리즘에 따라서 p2만 계속 앞으로 당겨지므로 (1, 4), (1, 3), (1, 2) 순으로 비교를 하게 되고 답을 도출할 수 있게 된다.