자바 백준 2470번 문제 : 두 용액

문제 출처 : https://www.acmicpc.net/problem/2470

2470번: 두 용액

 

문제 :

 

풀이 :

항상 그렇듯이 억지로 풀 수는 있다. for문으로 돌리면 0에 가장 가까운 값 찾을 수 있다.

시간초과가 날뿐..

투포인터를 잡으면 된다. 잡아도 되나? 어떻게 O(N)으로 0에 가장 가까운 두 값만을 서치할 수 있지?

일단 Arrays.sort(arr) 해주고 투포인터의 국룰(?) lt와 rt를 양 끝으로 잡아본다.

쓸모없는 움직임(비교)를 하지 않으면 된다.

lt를 0, rt를 n-1로 잡았을 경우 arr[lt]와 arr[rt] 두 값의 합이 음수라고 생각해보자.

0에 가까워 지고 싶으면 여기서 값이 커져야한다. 그러므로 여기서 lt++를 해준다.

arr[lt]와 arr[rt] 두 값의 합이 양수라면 값이 작아져야 절대값이 0에 가까워지므로 rt--를 해준다.

이렇게 lt가 rt보다 커질 때 까지 반복시키면 O(N)으로 비교해야 할 값들끼리만 비교할 수 있다.

 

소스코드 :

import java.util.*;
import java.io.*;
public class Main {
	public StringBuilder solution(int n, int[] arr) {
		StringBuilder sb = new StringBuilder();
		Arrays.sort(arr);
		int lt = 0, rt = n-1;
		int num1 = arr[0], num2 = arr[n-1];
		int minSum = Integer.MAX_VALUE;
		while(lt < rt) {
			// arr[lt] + arr[rt] 양수일 경우 값을 줄인다. 즉, rt--
			if (arr[lt] + arr[rt] > 0) {
				//minSum = Math.min(minSum, Math.abs(arr[lt] + arr[rt]));
				if (minSum > Math.abs(arr[lt] + arr[rt])) {
					minSum = Math.abs(arr[lt] + arr[rt]);
					num1 = arr[lt];
					num2 = arr[rt];
				}
				rt--;
			}
			// arr[lt] + arr[rt] 음수일 경우 값을 키운다. 즉 lt++
			else if(arr[lt] + arr[rt] < 0) {
				if (minSum > Math.abs(arr[lt] + arr[rt])) {
					minSum = Math.abs(arr[lt] + arr[rt]);
					num1 = arr[lt];
					num2 = arr[rt];
				}
				lt++;
			}
			// arr[lt] + arr[rt]가 0이면 바로 출력
			else if (arr[lt] + arr[rt] == 0) {
				sb.setLength(0);
				sb.append(arr[lt]).append(" ").append(arr[rt]);
				return sb;
			}
		}
		return sb.append(num1).append(" ").append(num2);
	}
    
	public static void main(String[] args) throws IOException {
	    Main T = new Main();
	    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());
		}
		System.out.println(T.solution(n, arr));
		br.close();
	}
}

 

 

후기 : 

이 문제 2달전이였나 방학 때 봤었는데 그때는 풀다가 잘 모르겠어서 포기했었는데

오늘 이 문제 다시 보니까 투포인터 잡으면 바로 풀리겠다 싶어서 코딩했는데

실수없이 한 번에 통과되었다. 감동적이다..