[ 백준 2470번 두 용액 ] 문제 풀이(Java) - 투 포인터 문제 풀이

 

투 포인터 문제를 풀어보았습니다.

오랜만에 알고리즘 문제 풀이 포스팅을 진행하는 것 같습니다..ㅋㅋ 앞으로 열심히해야짓..

 

 

문제보기

www.acmicpc.net/problem/2470

2470번: 두 용액

 

나의 풀이

 

문제는 간단합니다. 용액의 특성값을 나타내고 있는 배열이 주어진 뒤, 해당 배열에서 두 개의 용액을 합쳤을 때 합친 용액의 특성 값이 0에 가장 가까운 두 용액을 고르면 되는 문제입니다. 

 

가장 쉽게 떠올릴 수 있는 방법으로는 for문 두 개를 이용해서 모든 배열의 쌍에 대해 조사하는 방법이 있습니다. 그런데 이 방법은 안되는 이유가 N의 최대값이 100,000이라서 최대 연산 개수가 O(N^2) == O(10^10)이라서 시간초과가 나게 됩니다...

 

이전 포스팅에서 시간초과가 날 경우 떠올릴 수 있는 방법으로는

 

dp

그리디

이분탐색

투포인터

 

가 있다고 한 적이 있는데요! 여기서는 투 포인터 방법을 이용하도록 하겠습니다.

 

투 포인터는 start, end 두 개의 포인터를 이용해 조작하는 방법입니다.

먼저, 용액의 특성값이 담긴 배열을 오름차순으로 정렬해준 뒤, start와 end 포인터의 초기값으로 start는 0, end는 배열의 가장 마지막 원소를 가리키게 해줍니다.

 

시뮬레이션 과정

1. start와 end 포인터가 만날 때까지 반복

   - 현재 start와 end 포인터가 가리키는 두 용액의 특성 값 합을 구하고, 결과값 업데이트

   - start 포인터를 1 증가시켰을 때와 end 포인터를 1 증가시켰을 때의 값을 비교하여 0에 더 가까운 쪽으로 포인터 값 증가시키기

 

 

코드

 

//백준 2470번 두 용액
//투 포인터 알고리즘

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class N_2470 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] A = new int[N];

		String[] arr = br.readLine().split(" ");
		for (int i = 0; i < N; i++)
			A[i] = Integer.parseInt(arr[i]);

		Arrays.sort(A);
		int start = 0;
		int end = A.length - 1;
		long result = Integer.MAX_VALUE;
		int answer1 = 0;
		int answer2 = 0;

		while (start != end) {
			if (result > Math.abs(A[end] + A[start])) {
				result = Math.abs(A[end] + A[start]);
				answer1 = A[start];
				answer2 = A[end];
			}

			if (Math.abs(A[start] + A[end - 1]) < Math.abs(A[start + 1] + A[end])) {
				end--;
			} else {
				start++;
			}

		}

		System.out.println(answer1 + " " + answer2);
	}

}