백준 - 세 용액(2473)

오늘 풀어본 문제는 ⭐세 용액 이다!

친구가 추천해줘서 풀게 되었는데 좋은 문제라고 생각했다.

1. 문제 요약

• 같은 양의 세 가지 용액을 혼합한 용액 값 : 각 용액 값의 합
• 같은 양의 세 가지 용액을 혼합해 용액 값이 0에 가깝도록 만드려고 함.
• 용액의 특성값은 모두 다르다.

2. 입출력

[입력]

• 전체 용액 수 N (3<=N<=5000)
• 양수 용액 값 1~10억
• 음수 용액 값 -1~-10억

[출력]

• 조건에 맞는 세 가지 용액 값을 오름차순 정렬
• 동일 조건으로 정답이 여러개가 나온다면, 아무거나 출력할 것.

3. 알고리즘

이 문제는 투포인터를 활용한다.

1. 배열을 오름차순한다.
2. for문으로 i를 0에서 N-2까지 돌린다.
3. 투 포인터 l과 R을 세팅한다.
   • l = i+1;
   • r = N-1;
4. 이제 l<r인 동안, 인덱스 i,l,r 에 해당하는 용액의 합이 현재 가장 0에 가까운지 확인한다.
5. 만약 합이 양수였다면, 더해지는 값이 더 작아져야 하기에 r--,
   만약 합이 음수였다면, 더해지는 값이 더 커져야 하기에 l++를 진행한다.

4. 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());

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

        Arrays.sort(a);

        long bestAbs = Long.MAX_VALUE;
        long x = 0, y = 0, z = 0;

        for (int i = 0; i < N - 2; i++) {
            int l = i + 1;
            int r = N - 1;

            while (l < r) {
                long sum = (long) a[i] + a[l] + a[r];

                long abs = Math.abs(sum);
                if (abs < bestAbs) {
                    bestAbs = abs;
                    x = a[i]; y = a[l]; z = a[r];
                    if (bestAbs == 0) {
                        System.out.println(x + " " + y + " " + z);
                        return;
                    }
                }

                if (sum > 0) r--;
                else l++;
            }
        }

        System.out.println(x + " " + y + " " + z);
    }
}

이 코드에서 주의할 점 한 가지는

long sum = (long) a[i] + a[l] + a[r];

이 부분이다. 각 용액값은 +-10억으로 int 자료형에서 해결 가능하지만, 이렇게 3가지의 용액이 합쳐지는 구간은 int 범위를 넘을 수도 있기에 꼭 (long)으로 타입캐스팅을 해줘야 한다.

그래야 합이 int 범위가 아닌 long으로 인식 되어서 오버플로우가 안난다.