백준 2470번 - 두 용액(java)

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

2470번: 두 용액

 

투 포인터와 친해져야겠다는 생각으로 풀어본 문제

투 포인터 문제라는 것을 알고 시작하긴 했지만 그래도 스스로의 힘으로 풀었다!

 

💡 아이디어

• 이중 for문을 돌리면 반드시 터진다.
• 배열을 정렬한다. 정렬된 상태여야 포인터를 어떤 방향으로 옮길지 결정할 수 있었다. 정렬은 O(nlogn)이므로 터지지 않는다고 판단했다.
• 처음에는 2개의 포인터 모두 시작 부분에 놓고 시작했는데 합이 가장 크거나 작은 2개의 값을 찾는 것이 아니라 합이 0에 가까운 2개의 값을 찾는 거라 양 끝에 두는 게 나을 것 같았다.
• 앞에서부터 시작하는 포인터는 s(start), 뒤에서부터 시작하는 포인터는 e(end)로 두었다.
• 두 수의 합이 음수이면 합이 0에 가까워지려면 더하는 수가 커져야 하므로 s를 한칸 뒤로 옮기고,
• 두 수의 합이 양수이면 합이 0에 가까워지려면 더하는 수가 작아져야 하므로 e를 한칸 앞으로 옮겼다.

💡 코드

package TwoPointer;

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

public class BOJ_G5_2470_두용액 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] 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 s = 0, e = N - 1; //2개의 포인터(배열의 인덱스)
        int curSum = arr[s] + arr[e]; //현재까지 0과 가장 가까운 합
        int a = arr[s], b = arr[e]; //현재 합이 0과 가장 가까운 두 수

        while (s < e) {
            int sum = arr[s] + arr[e]; //두 수의 합

            if (sum == 0) { //합이 0이면 바로 종료
                a = arr[s];
                b = arr[e];
                break;
            }

            if (Math.abs(sum) < Math.abs(curSum)) { //0에 가장 가까운 2개의 수 갱신
                a = arr[s];
                b = arr[e];
                curSum = sum;
            }
            if (sum < 0) { //두 수의 합이 음수인 경우 start 값을 늘려야 합에 0으로 가까워짐
                s++;
            }
            if (sum > 0) { //두 수의 합이 양수인 경우 end 값을 줄여야 합에 0으로 가까워짐
                e--;
            }
        }
        System.out.println(a + " " + b);
    }
}