BOJ 2473 세 용액(Java)

문제 탐색하기

용액 문제의 응용 문제다.

• 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고,
• 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.
• 같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의하고,
• 같은 양의 세 가지 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.
• N은 3 이상 5,000 이하의 정수
• 용액의 특성값은 -1,000,000,000 이상 1,000,000,000 이하이며 각 특성값은 모두 상이하다.
• 출력은 세 용액의 특성값을 오름차순으로 출력한 값이다.

코드 설계하기

기존 용액 문제에서는 단순히 이진 탐색으로 구현했었다.

처음에는 3개니까 그냥 brute force로 해야 하나… 했는데 그렇게 하기에는 범위가 너무 커질 것 같았다. 그래서 기준점 값 하나를 설정하고 나머지 두 값을 이진탐색 시키는 방식으로 구현했다.

그리고 이번 문제에서는 정렬이 안 되어 있어서 정렬을 먼저 해줘야 한다.

1. 이진 탐색을 위한 정렬 (BS를 적용하려면 정렬이 되어 있어야 한다.)
2. 이진 탐색 + 포인터

으로 구현하기로 했다.

구현 방법

1. 입력으로 주어진 용액의 특성값 배열을 오름차순으로 정렬한다.
2. 첫 번째 용액을 고정하고, 나머지 두 용액을 투 포인터 방식으로 탐색한다.
   • 왼쪽 포인터는 첫 번째 용액의 다음 인덱스부터 시작
   • 오른쪽 포인터는 배열의 마지막 인덱스부터 시작
3. 세 용액의 합을 계산하고, 그 절댓값이 현재까지의 최소값보다 작으면 갱신한다.
4. 합이 0이면 바로 종료한다.
5. 합이 양수면 오른쪽 포인터를 왼쪽으로 이동, 음수면 왼쪽 포인터를 오른쪽으로 이동한다.
6. 모든 첫 번째 용액에 대해 위 과정을 반복한다.

시간 복잡도

• 정렬: O(N log N)
• 투 포인터 탐색: O(N²)
  • 첫 번째 용액을 고정하는데 O(N)
  • 각 고정된 용액에 대해 투 포인터로 탐색하는데 O(N)
• 전체 시간 복잡도: O(N²)

정답 코드 (Java)

import java.io.*;  
import java.util.*;  
  
public class b2473 {  
    private static int ml = 0, mm = 0, mr = 0; // 결과 값의 인덱스  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        int n = Integer.parseInt(br.readLine());  
        long[] arr = new long[n];  
  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        for(int i=0; i<n; i++) {  
            arr[i] = Long.parseLong(st.nextToken());  
        }  
  
        // 탐색을 위해 정렬  
        Arrays.sort(arr);  
  
        solution(n, arr);  
  
        System.out.println(arr[mm] + " " +arr[ml] + " " + arr[mr]);  
    }  
  
    private static void solution(int n, long[] arr) {  
        // 이진 탐색  
        long min = Long.MAX_VALUE;  
        // 투 포인터  
        for(int i = 0; i< n -2; i++) {  
            int left = i+1, right = n-1;  
  
            while (left < right) {  
                long sum = arr[left] + arr[right] + arr[i];  
                if(min > Math.abs(sum)) {  
                    // 합의 절댓값이 현재 min값보다 작은 경우 갱신  
                    min = Math.abs(sum);  
                    mm = i;  
                    ml = left;  
                    mr = right;  
                }  
                if(sum == 0) {  
                    // 합이 0이면 더 탐색할 필요 없음 종료  
                    mm = i;  
                    ml = left;  
                    mr = right;  
                    return;  
                }  
                if(sum > 0) { // 합이 양수일경우 우측 포인터 값 down
	                right--;  
                }else { // 합이 음수일경우 좌측 포인터 값 up
                    left++;  
                }  
            }  
        }  
    }  
}