BOJ - 2470 두 용액

2470 두 용액 : https://www.acmicpc.net/problem/2470

---

Problem

---

Solve

N이 100000이기 때문에 두 용액을 각각 비교하면 50000*50000이 나올수 있기 때문에 O(N)으로 풀수 있는 방법 중 투포인터를 사용했다.

두 용액의 합이 0과 가장 가까운 값을 찾아야하기 때문에 두 용액 합의 절댓값이 0과 가장 가까운 두 값을 찾으면 된다.

문제 풀이순서는 아래와 같다.

1. N개의 값을 저장한 배열(sequence)을 오름차순으로 정렬한다.
2. 두 용액의 합의 최대로 가질수 있는 값을 max로 start=0, end=배열의 크기-1로 초기화한다.
3. 두 용액 합(sequence[start]+sequence[end])의 절댓값을 max와 비교한다.
   • 두 용액 합의 절댓값이 max보다 작다면 두 용액간의 차이가 이전보다 적게 나는 것이므로 두 용액과 max를 갱신한다.
4. 두 용액 합이 음수이면 sequence[start]의 값이 sequence[end]보다 절댓값이 큰 것이기 때문에 start++를 해줌으로써 sequence[start]와 sequence[end]의 절댓값 차이를 줄여준다.(sequence는 오름차순으로 정렬되어있다.)
   두 용액 합이 양수이면 sequence[end]의 값이 sequence[start]보다 절댓값이 큰 것이므로 두 값의 차이를 줄이기 위해 end--를 해준다.
5. 위에서 갱신해준 두 용액의 값을 반환한다.

---

Code

public class 두용액 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());

		//용액 저장
		int[] sequence = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i=0;i<N;i++){
			sequence[i] = Integer.parseInt(st.nextToken());
		}

		//용액 오름차순으로 정렬
		Arrays.sort(sequence);

		int start=0;
		int end=sequence.length-1;
        //절댓값인 두 용액의 합이 가질수 있는 최댓값
		int max = 2000000000;
		int a=0;
		int b=0;
		while(start<end){
			int sum = sequence[start]+sequence[end];

			//두 용액의 특성값이 max보다 작다면 현재 까지의 특성값중 0에 가장 가까운 값이므로 두 용액과 특성값을 갱신해준다.
			if(Math.abs(sum)<max){
				a = sequence[start];
				b = sequence[end];
				max = Math.abs(sum);
			}

			//start는 음수의 값을 end는 양수의 값을 가리키고 있다.
            //start가 양수, end가 음수를 가리킬수도 있다.
			if(sum < 0){
            	//sum이 0보다 작다면 sequence[start]가 더 크기 때문에 두 용액의 특성값을 줄이기 위해 start를 증가시킨다.
                //start를 증가시키면 sequence[start]의 절댓값이 작아진다.
				start++;
			}else if(sum > 0){
            	//sum이 0보다 크다면 sequence[end]가 더 크기 때문에 end--
                //end--시 sequence[end]의 절댓값이 작아진다.
				end--;
			}else{
				break;
			}
		}
		StringBuilder sb = new StringBuilder();
		sb.append(a);
		sb.append(" ");
		sb.append(b);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

---

Result

---

Reference

https://bcp0109.tistory.com/55