99클럽 코테 스터디 5일차 TIL - Two Pointer

문제 💁🏻‍♂️

문제 링크 - 백준 2470 두 용액

해결 과정

문제를 읽고 나서, 어떻게 풀어야할까 많은 생각을 했다. 이 문제의 특징은 다음과 같다.

1. 음수와 양수가 혼합되어 있고, 두 숫자를 더해야한다.
2. 가능한 범위가 상당하다.
3. 두 숫자를 더했을 때의 절댓값이 0이거나 0에 가깝도록 만들어야한다.

사고 과정 ❗️

이 3가지 조건을 알아내고 나서는 어떻게 접근해야할 지 곰곰이 생각했다. 우선, 처음에는 음수와 양수를 따로 ArrayList에 각각 저장하고, 양수의 숫자들을 순회하면서 모든 음수값들을 체크해보려고 했다. 그렇지만, 그러기엔 양수의 개수와 음수의 개수가 50,000개라고 가정하면 50_000 * 50_000 = 2_500_000_000으로 시간을 초과할 것이다. 그러면 이 문제를 어떻게 해결하면 좋을까 ?

처음 생각한 방법으로 코드를 구현해보았지만, 정답을 도출해내지 못했다. 알고리즘 분류를 보니까 이분 탐색 & 투 포인터 라는 것을 확인했다. 투 포인터라는 것을 보고, 뭔가 감이 왔지만 코드 구현이 쉽지 않아서 풀이가 담긴 블로그를 열람했다. 핵심 로직은 다음과 같았다.

1. 양 끝 인덱스에서 시작한다.
2. 두 인덱스의 숫자를 더했을 때,
   2-1. 음수라면 -> 양수로 만들기 위해서 왼쪽 인덱스를 오른쪽으로 움직인다.
   2-2. 양수라면 -> 음수로 만들기 위해서 오른쪽 인덱스를 왼쪽으로 움직인다.
   2-3. 즉, 더했을 때의 절댓값을 0과 가깝게 만들기 위함이다.
3. 지속적으로 절댓값을 갱신한다.

이런 로직으로 코드를 짜고 제출하니 정답 판정을 받을 수 있었다. 코드가 이분 탐색과 매우 닮아있는 것을 보니, 이분탐색 로직을 조금 변형하면 투포인터 풀이가 될 수 있다는 것을 깨달았다. 내일 다시 풀어봐야지 :)

코드

정답 코드

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
    static int[] arr;

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

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

        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(arr);

        int[] res = bs();
        System.out.printf("%d %d\n", res[0], res[1]);

    }

    private static int[] bs() {

        int left = 0;
        int right = N - 1;

        int MIN = Integer.MAX_VALUE;
        int[] res = null;

        // 모든 숫자가 양수인 경우
        if (arr[left] > 0)
            return new int[]{arr[left], arr[left + 1]};

        // 모든 숫자가 음수인 경우
        if (arr[right] < 0)
            return new int[]{arr[right - 1], arr[right]};

        // 양수와 음수 모두 존재하는 경우
        while (left < right) {

            int sum = arr[left] + arr[right];
            if (Math.abs(sum) < MIN) {
                MIN = Math.abs(sum);
                res = new int[]{arr[left], arr[right]};
            }

            if (sum == 0)
                return new int[]{arr[left], arr[right]};
            else if (sum < 0) {
                left++;
            } else
                right--;
        }

        return res;
    }

}

Reference

• https://velog.io/@richsubin/백준-2470번-두-용액-JAVA