[BOJ] 백준 2473 - 세 용액 풀이

1. 문제

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

2473번: 세 용액

2. 풀이

• 용액의 특성 값의 범위가 -10억 ~ +10억 까지이므로 int형으로 하면 범위를 초과하므로 합을 구하는 변수나 long형으로 선언한다. (10억 + 10억 + 10억 = 30억 OR (-10억) + (-10억) + (-10억) = -30억이므로 int의 한계인 -21억 ~ +21억의 범위를 넘는다.)
• 주요 자료구조
  • List<Long> numList : 용액의 특성들을 저장할 리스트
• 우선 Two Pointer 탐색을 위해 numList에 용액의 특성들을 입력 받고 오름차순으로 정렬한다.
• 그 후 1부터 N - 2까지 반복문을 돌면서 이분탐색 함수를 실행한다.
  • 왜 1부터 N - 2까지 도는가?
    • 그 이유는 용액을 겹쳐서 고르면 안되므로 내 왼쪽의 최솟값 (0)보다 하나 큰 1 부터 내 오른쪽의 최대값(N - 1)보다 하나 작은 값을 mid 인덱스 값으로 설정해야 하기 때문이다.
• Two Pointer 함수에서는 left 인덱스를 0, right 인덱스를 리스트의 사이즈 - 1만큼, mid 인덱스를 반복문에서 넘겨받은 인자 값으로 한다.
• 설정한 인덱스에 맞는 용액의 특성 값을 리스트에서 꺼내와 합(hap)을 구한다.
• 이 합의 절댓값이 result보다 작거나 같다면 result, leftResult, rightResult, midResult에 용액 값을 갱신한다.
  • 절댓값으로 판단하는 이유는 무엇일까?
    • 문제에서 원하는 것은 0에 가까운 용액의 합이다.
    • -35와 +27중 0에 가까운 값은 +27이다.
    • 따라서 절대값으로 result와 판단해야 하는 것이다.
• 합을 판단했다면 이제 인덱스를 판단할 차례이다.
  • hap > 0
    • 합이 0보다 크다는 얘기는 0에 가까워지기 위해서 나보다 큰 값을 가지는 용액의 인덱스를 줄여야한다. 따라서 right의 값을 하나 줄인다. 이 때 이미 판단한 값은 고르면 안되므로 right - 1부터 반복문을 시작하여 mid 값이 아닌 값을 선택한다. 
  •  hap < 0
    
    • 합이 0보다 작다는 얘기는 0에 가까워지기 위해서 나보다 작은 값을 가지는 용액의 인덱스를 늘려야한다. 따라서 left의 값을 하나 늘린다. 이 때 이미 판단한 값은 고르면 안되므로 left + 1부터 반복문을 시작하여 mid 값이 아닌 값을 선택한다.
• 마지막으로 leftResult, rightResult, midResult를 오름차순으로 출력하면 정답!!
  
  
  

3. 소스 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N; // 용액수
    static List<Long> numList = new ArrayList<>(); // 용액 리스트
    static long result = Long.MAX_VALUE;

    static long leftResult = 0;
    static long midResult = 0;
    static long rightResult = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            numList.add(Long.parseLong(st.nextToken()));
        }

        // 이분탐색을 위한 오름차순 정렬
        Collections.sort(numList);

        // 이분 탐색 함수 시작
        for (int i = 1; i < N - 1; i++) {
            twoPointSearch(i);
        }

        //결과 출력
        List<Long> sortList = new ArrayList<>();
        sortList.add(leftResult);
        sortList.add(midResult);
        sortList.add(rightResult);
        Collections.sort(sortList);

        bw.write(sortList.get(0) + " " + sortList.get(1) + " " + sortList.get(2));
        bw.flush();
        bw.close();
        br.close();
    }

    // Two Pointer 함수
    private static void twoPointSearch(int idx) {
        int left = 0;
        int right = numList.size() - 1;
        int mid = idx;

        while (left < right) {

            long hap = 0;
            hap = numList.get(mid) + numList.get(left) + numList.get(right);

            // 0에 가까운 값이므로 절대값으로 계산
            if (Math.abs(hap) <= Math.abs(result)) {
                result = Math.abs(hap);
                leftResult = numList.get(left);
                midResult = numList.get(mid);
                rightResult = numList.get(right);
            }

            // 합이 0보다 크다는 것은 나보다 큰 값을 가지는 배열의 인덱스를 줄여야 한다.
            if (hap > 0) {
                for (int i = right - 1; i >= 0; i--) {
                    if (i != mid) {
                        right = i;
                        break;
                    }
                }
            } else {    // 합이 0보다 작다는 것은 나보다 작은 값을 가지는 배열의 인덱스를 늘려야 한다.
                for (int i = left + 1; i < numList.size(); i++) {
                    if (i != mid) {
                        left = i;
                        break;
                    }
                }
            }
        }
    }
}

4. 배운 점

• 3개의 인덱스를 가지고도 Two Pointer를 쓸 수 있다.
  
  

5. 점수

75 / 100