백준 2473번 : 세 용액 [자바]

 

🧫 문제 분석

 

✔️ 출처

세 용액 골드 3

 

📖 문제

 

기존 두 용액 문제에서

전체를 투포인터로 두고 투 포인터를 제외한 곳을 이분탐색으로 해서 풀려했으나

당연히 모든 용액이 3가지씩 조합되지 않기에 계속해서 틀렸다.

 

나의 약한 부분중 하나가 이런 부분인 것 같다.

 

꼭 3개이상 , 여러개 등 조합해야하는 문제나 비슷한 문제들을 만나면

하나를 고정하고 푼다는 이런 생각을 떠올리지 못한다. 

 

까먹지 않기위해 블로그에 박제한다. 

 

그리고 기껏 long type으로 계산해야한다고 메모해놓고 또 (long)으로 캐스팅안해서 틀렸다... 

---

🔅 풀이 시도 

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

public class Main {
    static int[] solutions;
    static int[] answer;
    static long min;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        solutions = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 용액 특성값 초기화
        for (int i = 0; i < n; i++) {
            solutions[i] = Integer.parseInt(st.nextToken());
        }

        // 특성값을 오름차순 정렬
        Arrays.sort(solutions);

        answer = new int[3];
        min = Long.MAX_VALUE;

        // 투포인터 + 이분탐색
        int left = 0, right = n - 1;
        while (left <= right) {

            // 먼저 두개의 용액을 섞는다.
            int sum = solutions[left] + solutions[right];
            addThirdSolution(left, right, sum); // 0에 가깝게 만들어주는 3번째 용액을 찾는다.

            if (sum < 0) left++;
            else right--;

        }

        for (int val : answer) {
            sb.append(val).append(" ");
        }
        System.out.println(sb.toString());

    }

    // 0에 가깝게 만들어주는 3번째 용액을 찾아서 넣는다.
    private static void addThirdSolution(int left, int right, int sum) {
        int start = left + 1, end = right - 1;
        while (start <= end) {

            int mid = (start + end) >>> 1;
            long sum3 = sum + solutions[mid]; // 3개의 용액 합 (3개 합이 10억 + 10억 + 10억일 수 있으므로 long타입으로)
            long tmpSum = Math.abs(sum3); // 3개의 합의 절댓값

            // 기존 0에 가까운 값보다 더 가깝다면 갱신
            if (min > tmpSum) {
                answer[0] = solutions[left];
                answer[1] = solutions[mid];
                answer[2] = solutions[right];
                min = tmpSum;
            }

            // 3개의 합이 음수라면 0에 가깝게 하기 위해 큰 값 범위로 줄임
            if (sum3 < 0) {
                start = mid + 1;

                // 3개의 합이 양수라면 0에 가깝게 하기 위해 작은 값 범위로 줄임
            } else {
                end = mid - 1;
            }

        }
    }


}

🔅 문제풀이

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

public class Main {
    static int[] solutions;
    static int[] answer;
    static long min;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        solutions = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 용액 특성값 초기화
        for (int i = 0; i < n; i++) {
            solutions[i] = Integer.parseInt(st.nextToken());
        }

        // 특성값을 오름차순 정렬
        Arrays.sort(solutions);

        answer = new int[3];
        min = Long.MAX_VALUE;

		// 1개를 미리 정하고 나머지에 대해서 투포인터 탐색
        for (int i = 0; i < n - 2; i++) {
        
            int left = i + 1, right = n - 1;
            while (left < right) {
                long sum = (long)solutions[i] + solutions[left] + solutions[right];
				
                // 현재 합이 0에 가깝다면 갱신
                if (min > Math.abs(sum)) {
                    answer[0] = solutions[i];
                    answer[1] = solutions[left];
                    answer[2] = solutions[right];
                    min = Math.abs(sum);
                }

                if (sum == 0) {
                    break;
                }

                if (sum < 0) left++;
                else right--;
            }
        }

        for (int val : answer) {
            sb.append(val).append(" ");
        }

        System.out.println(sb.toString());

    }
}

 

 

❗ 오답노트 / 필요한 지식

1.  문제를 한가지 방법이 아닌 여러가지 방법으로 생각하자. 여러개일 경우 몇개는 고정하고 생각하는 방식을 떠올리자.