[투 포인터, JAVA] 백준 - 2467

문제: https://www.acmicpc.net/problem/2467

2467번: 용액

---

투 포인터에 대해서 공부한다고 했을 때 알고리즘 단톡방에 계신 분께서 추천해주신 문제다.
필자는 이 문제로 두개의 포인터가 같은 방향으로 이동하는 것과 서로 다른 방향에서 진행되는 알고리즘의 차이를 알 수 있었다.
당연한 얘기지만 이 문제를 풀 때 정말 머리를 쥐어 싸맸던 것으로 기억한다.
이제 따끈따끈하게 실버가 된 뉴비에게 골드 문제는 아직까지도 많이 어려웠다.
하지만 나도 할 수 있었던 만큼 다른 분들도 투 포인터 알고리즘을 알고만 있다면 할 수 있을 것이라고 생각한다.
지금부터 문제 분석부터 차근차근 넘어가보자.

일단 문제에서 요구하는 것 자체는 그리 어렵지 않다.
두 용액의 합이 최대한 0과 가까우면 되는 문제이다. 출력은 그 두 용액을 출력하면 된다.
하지만 여기서 문제점이 생긴다. 더해서 0과 가장 가까운 값을 찾으려면 어떻게 해야 하지?
즉, 우린 여기서 투 포인터 + 근사값 알고리즘 이렇게 같이 알아야 이 문제를 풀 수 있다.
물론 이분탐색으로도 풀 수 있지만, 일단 이 글에선 투 포인터로 주제를 잡고 풀겠다.

0과 근사한 값을 구하려면 어떻게 해야 할까?
일단 0에서 얼마나 떨어져있는지를 체크하고, 이 값과 비교할 이전의 최소 거리값이 있어야 할 것이다.
그러기 위해선 우린 절대값을 사용해야 한다. 왜냐하면 절대값 자체가 수직선의 거리를 뜻하기 때문이다.
그리고 더해서 나온 최소값이 이전의 최소 거리값보다 작다면 최소값을 바꿔주고 더해지는 값들을 답으로 지정하면 된다.
그리고 우린 그 더해지는 값들을 투 포인터로 찾으면 된다. 말로 하면 어렵지만, 그림으로 보면 쉬울 것이다.

알고리즘 흐름

정리하자면
① 서로 더해지는 숫자들은 투 포인터 알고리즘을 이용해서 바꿔준다. (0을 기준으로)
② 더한 값이 0이랑 가까운지 체크하는건 근사값 알고리즘을 사용한다.

그럼 이제 코드를 살펴보자.

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

public class BOJ_2467_4 {
	public static void main(String[] args) throws IOException{
		// TODO 백준 2467
		
        //입력을 빨리 받기 위한 BufferedReader 클래스와 숫자들을 파싱할 STringTokenizer 클래스 객체
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken()); //용액의 개수
		int[] nums = new int[N]; //용액 개수만큼의 배열 선언
		
        //st 변수 초기화. BufferedReader 클래스는 한 줄씩만 읽어오기 때문에,
        //입력받는 줄이 달라진다면 st를 초기화해줘야 한다.
		st = new StringTokenizer(br.readLine());
        
        //용액의 숫자들을 입력받는 반복문
		for(int i=0; i<N; i++) { 
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
        //start는 배열의 시작 인덱스, end는 배열의 끝 인덱스,
        //asnwer1, answer2는 0과 더해서 0과 가장 가까운 2개의 용액 값을 저장할 변수들이다.
        //min은 이전 최소값이다. 하지만 지금은 비교 대상이 없기 때문에(아직 반복문에 들어가지 않음) 
        //Long의 최대값으로 저장해놓은 상태다.
		int start = 0, end = N-1, answer1 = 0, answer2 = 0;
		long min = Long.MAX_VALUE;
		
        //투 포인터 알고리즘 + 근사값 알고리즘
		while(start < end) {
        	//더한 값은 반복이 돌 때마다 변해야 하므로 반복문 안에서 선언하고 값을 더해준다.
            //abs는 더한 값의 절대값이다.
            //따로 저장하는 이유는 sum 값의 범위에 따라서 
            //start를 증가 시키거나 end를 감소시켜야 하기 때문이다.
			long sum = nums[start] + nums[end];
			long abs = Math.abs(sum);
			
            //만약에 이전 합이 현재 더한 것보다 크다면 - 새로운 최소값 탄생
            //min의 값을 바꿔주고 answer1, 2에다가 현재 용액의 값들을 저장해준다.
            //저장해주고 만약 sum이 0이라면 이미 0과 가장 가까운 용액의 값을 찾은 것이므로
            //반복문을 종료시켜준다.
			if(abs < min) {
				min = abs;
				answer1 = nums[start];
				answer2 = nums[end];
				
				if(sum == 0) {
					break;
				}
			}
			
            //만약에 sum이 0보다 작다면 - 0과 가장 가까운 값이 되어야 하므로
            //0보다 작은 값이 나온다면 start 인덱스를 증가시켜주고,
            //반대의 경우엔 end를 줄여준다.
			if(sum < 0) {
				++start;
			} else {
				--end;
			}
		}
		
        //반복문이 종료된다면 두 용액들을 출력해준다.
		System.out.println(answer1+" "+answer2);
	}
}