[백준] 2467번 : 용액 (JAVA/자바)

[문제 링크]

https://www.acmicpc.net/problem/2467

문제 설명

주어진 용액들 중에서 서로 다른 2개의 용액을 혼합해서 나온 값이 0에 가장 가까운 용액을 만들어 내는 두 용액을 구한다.

 

 

 

 

문제 풀이

알고리즘 분류

• 투포인터

 

용액이 오름차순 정렬되어 있는 상태이므로 가장 첫 번째 값 인덱스(left)와 가장 마지막 값 인덱스(right)를 포인터로 지정한 후, 배열이 안쪽 방향으로 두 포인터를 움직이면서 0에 가까운 두 수를 구한다.

 

1. 0과 n-1 를 투 포인터 left, right로 지정한다.

2. left와 right 인덱스가 가리키는 두 값을 더한 값(sum)을 구한다.

3. Math.abs(sum) < minValue  sum 절대값이 현재 저장된 값보다 작을 경우 현재 저장된 값 업데이트

4-1. sum >= 0  0보다 크거나 같을 경우 오른쪽 포인터 이동(right 감소)

4-2. sum < 0  0보다 작을 경우 왼쪽 포인터 이동(left 증가)

 

 

전체코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());    //전체 용액의 수

        int[] array = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

        int left = 0;
        int right = n - 1;

        int mixL = 0;
        int mixR = 0;
        long minValue = Long.MIN_VALUE;

        while(left < right) {
            long sum = array[left] + array[right];
            if(Math.abs(sum) < minValue) {
                mixL = left;
                mixR = right;
                minValue = Math.abs(sum);
            }

            if(sum >= 0) {
                //둘 다 양수이거나
                //|array[left]| < |array[right]|(양수의 절댓값이 더 큰 경우)
                right--;
            } else {
                //둘 다 음수이거나
                //|array[left]| > |array[right]|(음수의 절댓값이 더 큰 경우
                left++;
            }
        }
        System.out.println(array[mixL] + " " + array[mixR]);
    }
}