백준 2470 java - 두 용액(투 포인터)

문제, 입출력, 테스트케이스

package boj;

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

public class Boj_2470 {
	public static void main(String[] args) throws Exception {
		
		// 완탐 불가능
		//-99, -2, -1, 4, 98
		// O              O
		//      O   O  
		// O           O
		// O               O
		//     O   O   
		//     O       O
		//     O           O
		//         O   O
		//         O       O
		//             O   O 
		//
		
		// O   O
		// 4, 98
		// O, O  =  
		// 이미 0이 된 경우는 그냥 답
		// 왼쪽 끝 커서, 오른쪽 끝 커서로 시작
		// 오른쪽 커서 움직이다가 이전보다 0에서 멀어지면 왼쪽 커서 움직임
		// 왼쪽커서 < 오른쪽커서 일때까지 돌림
		BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int arr[] = new int[N];
		StringTokenizer stz = new StringTokenizer(br.readLine());
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(stz.nextToken());
		}
		
		Arrays.sort(arr);
		int leftCursor = 0;
		int rightCursor = N-1;
		
		int min = Integer.MAX_VALUE;
		int answer[] = new int[2];
		while(leftCursor < rightCursor && leftCursor >= 0 && rightCursor < N) {
			
			int absSum = Math.abs(arr[leftCursor] + arr[rightCursor]);
			int tempSum = arr[leftCursor] + arr[rightCursor];
			if(tempSum == 0) {
				answer[0] = arr[leftCursor];
				answer[1] = arr[rightCursor];
				break;
			}
			if(absSum < min) {
				min = absSum;
				answer[0] = arr[leftCursor];
				answer[1] = arr[rightCursor];
			}
			if(tempSum > 0) {
				rightCursor--;
			}else {
				leftCursor++;
			}
		}
		
		System.out.println(answer[0] + " " + answer[1]);
		
	}
}

해당 문제는 50분 동안 이왜틀만 반복하다가 구선생님(구글)의 도움으로 풀게 된 문제다... 약간 뇌가 말랑말랑하지 못했다...!

 

<문제 접근/풀이과정>
입력 조건 
전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다.
둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다.
이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.
-> 주어진 시간 제한은 1초이므로 O(NlogN)으로 풀어내야 한다. 투포인터를 쓰면 N으로 풀 수 있다.
1. 이미 0이 된 경우는 그냥 답
2. 투포인터를 사용하기 위해 정렬 후 왼쪽 끝 커서, 오른쪽 끝 커서로 시작
3. 양수로만 이루어진 경우 오른쪽커서를 -1만큼 계속 움직이게 됨
4. 음수로만 이루어진 경우 왼쪽커서를 +1만큼 계속 움직이게 됨
5. 양수, 음수로 이루어진 경우 왼쪽 오른쪽 커서가 0에 수렴되게 -1, +1 움직이게 됨
6. 결론: 합계가 0보다 큰 경우 오른쪽 커서를 -1만큼 움직임, 합계가 0보다 작은 경우 왼쪽 커서를 +1만큼 움직임.
5. 왼쪽커서 < 오른쪽커서 일때까지 돌림

투포인터 응용하면 된건데 너무 편하게 풀려고 하다가 오히려 규칙을 못 찾아냈다 ㅜㅜ