[99클럽 코테 스터디] 5일차 TIL - 백준 2470번 두 용액

 

오늘의 문제는 백준 2470번 '두 용액' 이었다.

 

 

 

이번 문제는 '투 포인터'를 활용하는 문제였다.

처음에는 단순하게 모든 조합을 확인하는 방식으로 풀려고 했지만, N이 최대 100,000까지 주어지기 때문에 O(N^2)로 접근하면 시간 초과가 날 가능성이 컸다.

이번 문제의 알고리즘 분류를 보니 '이분 탐색'과 '두 포인터'가 있었다.

그래서 O(N log N)으로 풀 수 있는 투 포인터 방식을 사용하도록 했다.

 

 

문제 해결 과정

1. 배열을 정렬한다.
   • 음수는 왼쪽, 양수는 오른쪽에 위치하게 된다.
2. 투 포인터를 사용하여 최소 합을 찾는다.
   • 하나는 가장 왼쪽 (left = 0), 하나는 가장 오른쪽 (right = N-1) 에 배치한다.
   • 두 개의 용액을 더한 값이 0과 가까운지를 확인하면서 포인터를 조정한다.
3. 두 용액의 합이 0보다 작으면 left를 증가
   • 즉, 현재 합이 음수라는 것은 0에 가까워지기 위해서는 더 큰 값이 필요하다는 뜻이다.
4. 두 용액의 합이 0보다 크면 right를 감소
   • 즉, 현재 합이 양수라면 0에 가까워지려면 더 작은 값이 필요하다.
5. 절댓값이 최소가 되는 두 수를 계속 갱신하면서 탐색한다.

코드

package Boj;

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

public class Boj2470 {
    static int[] arr;
    static int N;
    static int minSum = Integer.MAX_VALUE;
    static int ans1, ans2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];

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

        Arrays.sort(arr);

        int left = 0, right = N - 1;

        while (left < right) {
            int sum = arr[left] + arr[right];

            if (Math.abs(sum) < minSum) {
                minSum = Math.abs(sum);
                ans1 = arr[left];
                ans2 = arr[right];
            }

            if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }

        System.out.println(ans1 + " " + ans2);
    }
}

 

 

시간 복잡도 분석

• 정렬: O(N log N)
• 투 포인터 탐색: O(N)
• 총 시간 복잡도: O(N log N)

투 포인터를 활용하면 O(N^2)이 아닌 O(N log N)으로 문제를 해결할 수 있다.

 

 

오늘의 회고

이번 문제를 통해 투 포인터의 핵심 개념을 다시 한 번 정리할 수 있었다. 투 포인터는 정렬된 배열에서 특정 조건을 만족하는 값을 빠르게 찾을 때 유용한 방법이라는 걸 다시 확인했다.

이제 투 포인터를 활용하는 다른 유형의 문제도 연습해 봐야겠다!