2467 - 용액

이 문제는 용액의 특성값이 오름차순으로 정렬되어 주어지면, 두 용액을 섞어 특성값이 0에 가장 가깝도록 할 수 있는 특정한 용액 두 개를 찾아야 하는 문제이다.

문제에 나와있는 예제 테스트케이스만 보면 왼쪽과 오른쪽 원소를 대칭적으로 더했을 때 0에 가장 가까워지는 것처럼 보인다. 그러나 아래의 경우를 생각해보자

5
-5 7 8 9 10

이 경우에는 -5 + 10 보다는 -5 + 7 이 더 0에 가깝다. 따라서 대칭적으로 더하는 것이 항상 0에 가까운 조합을 만족시키지 않는다는 것을 알 수 있다.

그렇다면 어떻게 해야 이 문제를 풀 수 있을까? 여기서는 투 포인터 알고리즘을 사용해야 한다.

투 포인터로 이 문제를 푸는 방법을 간략히 설명하면 아래와 같다.

1. leftPtr=0, rightPtr=N-1 로 선언한다.
2. 두 포인터가 가리키는 원소 값의 합을 구한다.
3. 2.에서 구한 합이
   • 0보다 크면 : rightPtr--
   • 0보다 작으면 : leftPtr++
   • 0이면 : 반복문 탈출
4. leftPtr < rightPtr 이면 2. 로 돌아간다.

0에 가장 가까운 조합을 구해야 하므로 위 과정에서 추가로 2.에서 구한 합의 절대값을 minPh로 관리하고 매번 반복문을 돌 때마다 최소값을 확인해 minPh, minLeft, minRight를 업데이트하면 문제의 정답을 알 수 있다.

이러한 방법이 가능한 이유는 배열이 오름차순 정렬이므로, leftPtr을 오른쪽으로 옮기면 합이 증가하고, rightPtr을 왼쪽으로 옮기면 합이 감소하기 때문이다.

🔗 문제 링크

코드

용액의 총 개수 N과 용액의 특성도를 입력받는다. 투 포인터를 사용하려면 값이 정렬되어 있어야 하지만, 용액의 특성도가 오름차순으로 주어지므로 이 문제에서는 정렬할 필요가 없다.

public static void main(String[] args) throws IOException {
    int N = Integer.parseInt(br.readLine());
    long[] sols = new long[N+1];

    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) 
        sols[i] = Long.parseLong(st.nextToken());

포인터의 위치를 가리킬 leftPtr, rightPtr과 용액 특성도 절대값의 최소값을 관리할 minPh, 그리고 그때의 용액 특성도 조합을 저장할 minLeft, minRight를 선언하고 값을 각각 대입한다.

    int leftPtr = 0;
    int rightPtr = N-1;
    
    long minPh = Math.abs(sols[leftPtr] + sols[rightPtr]);
    long minLeft = sols[leftPtr];
    long minRight = sols[rightPtr];

leftPtr < rightPtr 인 동안 반복문을 돌며 투 포인터 알고리즘을 수행한다. 먼저 현재 포인터가 가리키고 있는 용액 특성도의 합을 구한다. 그런 다음 그 특성도의 절대값이 기존보다 작다면 minPh, minLeft, minRight를 업데이트한다.

다음으로, curPh > 0이라면 양수 특성도값을 줄이기 위해 rightPtr--을 수행하고, curPh < 0 이라면 음수 특성도값을 줄이기 위해 leftPtr++를 수행한다. curPh == 0이면 그 값이 최적값이므로 while문을 더 돌지 않고 break로 빠져나온다.

    while (leftPtr < rightPtr) {
        long curPh = sols[leftPtr] + sols[rightPtr];

        if (minPh > Math.abs(curPh)) {
            minPh = Math.abs(curPh);
            minLeft = sols[leftPtr];
            minRight = sols[rightPtr];
        }

        if (curPh > 0) rightPtr--;
        else if (curPh < 0) leftPtr++;
        else break;
    }

while 문을 빠져나오면 결과를 얻었다는 뜻이므로 minLeft, minRight를 출력하고 프로그램을 종료한다.

    System.out.println(minLeft + " " + minRight);
}

전체 코드

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        long[] sols = new long[N+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) 
            sols[i] = Long.parseLong(st.nextToken());
        
        int leftPtr = 0;
        int rightPtr = N-1;
        
        long minPh = Math.abs(sols[leftPtr] + sols[rightPtr]);
        long minLeft = sols[leftPtr];
        long minRight = sols[rightPtr];

        while (leftPtr < rightPtr) {
            long curPh = sols[leftPtr] + sols[rightPtr];

            if (minPh > Math.abs(curPh)) {
                minPh = Math.abs(curPh);
                minLeft = sols[leftPtr];
                minRight = sols[rightPtr];
            }

            if (curPh > 0) rightPtr--;
            else if (curPh < 0) leftPtr++;
            else break;
        }

        System.out.println(minLeft + " " + minRight);

    }
}

시간복잡도

투 포인터는 배열의 모든 원소를 최대 1번씩 방문하므로 최악의 경우 $N$ 개의 원소를 확인할 것이다. 따라서 이 알고리즘의 시간복잡도는 $O(N)$이다.