문제번호	제목	난이도
2467	용액	골드 5

2467번 용액

해결 코드:

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

public class Main {


    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());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int start = 0;
        int end = arr.length-1;
        int ans = Integer.MAX_VALUE;

        int a = 0;
        int b = 0;
        while(start < end){
            int sum = arr[start] + arr[end];
            if(ans > Math.abs(sum)){
                ans = Math.abs(sum);
                a = start;
                b = end;
            }
            if(sum < 0){
                start++;
            }else{
                end--;
            }
        }
        bw.write(arr[a] + " " + arr[b]);

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

고민의 시간과 해결 방법:

1. 양끝점의 합이라는 주어진 문제를 보고 투포인터와 이분탐색이 떠올랐다.
2. 하지만 이분탐색은 해당 문제를 해결하는데 적합한 방법이 아니다. 앞 뒤로 계속 더하면서 와야하는데 이분탐색은 그 중간을 기준으로 범위를 좁혀나가는 것이라 풀이에 맞지 않다.
3. 투포인터로 문제를 풀었다. start가 end보다 작은동안 순회를 계속한다
4. 각 순회마다 arr[start]와 arr[end]를 더한다. 그다음 0까지의 차이를 보기 위해 Matha.abs(sum)으로 ans와 비교한다. ans보다 작다면 ans에 해당 값을 넣고, 출력을 위한 a와 b에 arr[start]와 arr[end]를 넣는다
5. 이어서 만약 sum이 0보다 작다면 음수가 더 컸다는 의미이므로 왼쪽 포인터인 start를 증가시키고 0보다 크거나 같으면 양수가 더 크거나 같았다는 의미이므로 오른쪽 포인터인 end를 감소시켜서 범위를 좁혀나간다
6. 완성된 a와 b를 출력하면 정답이 된다.

문제 링크:

2467 - 용액