[백준] 2470 - 두 용액

[문제링크]

2470번: 두 용액

 

0. 두 포인터 문제

 

1. 두 포인터 사용을 위해 전체 입력값을 정렬해준다

• Arrays.sort는 최악 N제곱으로 나오는 함수이므로, Collections.sort를 이용했다

 

2. 양 끝 값을 초기 포인터로, 두 값의 차이를 초기 합(min)로 지정한다

 

3. 현재 포인터가 가리키는 용액의 합이 현재 min보다 작다면, 새로운 min으로 지정하고 포인터를 저장한다

 

4. 현재 포인터 용액의 합이 양수라면 + 용액이 약해져야하고, 음수라면 - 용액이 약해져야한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		ArrayList<Integer> num = new ArrayList<>(N);
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			num.add(pint(st.nextToken()));
		}
		
		Collections.sort(num);
		
		int fst=0, snd=N-1;
		int min = Math.abs( num.get(fst)+num.get(snd) );
		int minMinus=num.get(fst), minPlus=num.get(snd);
		
		while(fst<snd) {
			int cur = num.get(fst)+num.get(snd);
			if(Math.abs(cur)<min) {
				min = Math.abs(cur);
				minMinus=num.get(fst); minPlus=num.get(snd);
			}
			
			if(cur<0) {
				fst++;//- 용액 약화
			}
			else {
				snd--;//+ 용액 약화
			}
		}
		System.out.println(minMinus+" "+minPlus);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면