[Two Pointer] 용액

📌 문제

• 문제 링크 : https://www.acmicpc.net/problem/2467
• 문제 유형 : 투 포인터
• 문제 난이도 : 골드5

📌 문제 풀이

양쪽 끝에서 시작하는 투 포인터를 잡는다.
왼쪽에서 오른쪽으로 가는 것은 증가를 의미,
오른쪽에서 왼쪽으로 가는 것은 감소를 의미한다.

이 때, 왼쪽에서 오른쪽으로 움직이는 증가폭이 0에 더 가깝게 만들어 주는지,
오른쪽에서 왼쪽으로 움직이는 감소폭이 0에 더 가깝게 만들어주는지 알 수 없다.

즉, 증가하는 분과 감소하는 분 중 누가 더 0에 가깝게 만들어주는 지 알 수 없다.

그래서 왼쪽 이동후의 값과 오른쪽 이동후의 값을 비교해서 더 작은 쪽으로 움직인다.

▸ 그림 설명

• 위의 예에서 현재 arr[left] + arr[right] 의 값은 -8이다.

이 때, 음수의 값이 나왔으니 left 의 값을 증가시켜서 0에 가깝게 만들어야 되지 않을까 생각이 들 수 있다.

그러나, 0에 가깝게 라는 말은 0의 절대값을 의미한다.

위의 경우 음수값인데도 불구하고, right의 값을 감소시키는 것이 0에 더 가깝게 된다.

순회하는 pointer입장에서는 감소하는 값의 폭이 더 클지, 증가하는 값의 폭이 더 클지 모른다.

그래서 미리 arr[left+1] 과 arr[right+1] 의 값을 대조해보고, 더 0에 가까운 쪽으로 pointer가 움직인다.

📌 코드

public class Main {

    static int N;
    static int[] arr;

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

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        arr = new int[N];

        for(int i=0;i<N;i++){
            arr[i] = sc.nextInt();
        }

        int left = 0;
        int right = N-1;
        int min = Integer.MAX_VALUE;

        int leftV=0;
        int rightV=0;

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

            if(min > sum){
                min = sum;
                leftV = left;
                rightV = right;
            }

            int goLeft = Math.abs(arr[left+1]+arr[right]);
            int goRight = Math.abs(arr[left]+arr[right-1]);

            if(goLeft > goRight){
                right--;
            }else{
                left++;
            }
        }
        System.out.print(arr[leftV] + " " + arr[rightV]);
    }
}