BOJ - 2473 세 용액

leehyunjon·2022년 6월 30일

boj 투포인터

Algorithm

목록 보기

91/162

Problem

Solve

세 가지 용액을 반복문으로 돌리면 O(N^3)으로 시간초과가 발생한다.

하지만 투포인터를 이용한다면 O(N^2)으로 해결할 수 있다.
특정 용액(idx), 각 두 용액(left, right)를 이용한다.

풀이 방법은 아래와 같다.

용액을 오름차순 정렬한다.
특정 용액(idx), 각 투포인터를 이용한 용액(left, right)를 초기화한다.
- left = 0, right = N-1
sum = arr[idx] + arr[left] + arr[right]의 합을 통해 left와 right를 조절한다.
- sum > 0 이면 합을 줄이기 위해 right--
- sum < 0 이면 합을 늘리기 위해 left++
세 용액의 합이 0에 수렴하는지 비교하기 위해 sum의 절대값과 이전 합의 절대값과 비교하여 sum의 절대값이 더 0에 수렴한다면 합의 최소값을 갱신하고, 세 용액의 특성 값을 저장한다.
sum == 0이라면 더 이상 비교할 필요가 없기 때문에 갱신된 값을 반환한다.

주의할 점은 세 용액이 같은 용액으로 합을 구할 수 없고, 세 용액의 합은 최대 |30억|이기 때문에 long타입을 사용해줘야한다는 점이다.

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[] arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		//용액 오름차순 정렬
		Arrays.sort(arr);

		long result = Long.MAX_VALUE;
		int[] answer = new int[3];
        //특정 용액
		for (int i = 0; i < N; i++) {
        	//투포인터를 이용한 나머지 두 용액
			int left = 0;
			int right = N - 1;
            //투포인터를 이용한 두 용액이 사용했던 용액은 중복해서 확인할 필요가 없다.
			while(left<N && right>0 && left<right){
            	//같은 용액으로 합을 구할 수 없다.
				if(i == left){
					left++;
					continue;
				}
				//같은 용액으로 합을 구할 수 없다.
				if(i == right){
					right--;
					continue;
				}
                //세 용액의 합
				long sum = (long)arr[i]+arr[left]+arr[right];
                //세 용액의 합이 더 0에 수렴한다면 합과 세 용액 갱신
				if(result>Math.abs(sum)){
					result = Math.abs(sum);
					answer[0] = arr[i];
					answer[1] = arr[left];
					answer[2] = arr[right];
				}

				//세 용액의 합이 0이라면 더이상 비교할 필요가 없다.
				if(sum == 0){
					break;
				}
                //합이 0보다 크면 합의 크기를 줄여준다.
				if(sum>0) right--;
                //합이 0보다 작다면 합의 크기를 늘려준다.
				if(sum<0) left++;
			}
            //세 용액의 합이 0이라면 더이상 비교할 필요가 없다.
			if(result == 0) break;
		}

		//세 용액 사전순 정렬
		Arrays.sort(answer);

		StringBuilder sb = new StringBuilder();
		for(int n : answer){
			sb.append(n);
			sb.append(" ");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}