[BOJ/JAVA] 2473(세 용액)

1. Link

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

2. 풀이 과정

세 용액이라고 해서 처음에는 2중 for문 이후 Binary Search 탐색 방법 생각
그러나 투 포인터로 훨씬 간결하게 진행할 수 있다는 것을 판단하고 투 포인터로 문제를 풀었습니다.

• 해당 문제는 이분 탐색 또는 투 포인터 알고리즘을 직관적으로 떠오르게 하는 문제였습니다.

• 다만 구현에 있어 투 포인터가 더 수월한 감이 있으며, 이분 탐색으로 구현 가능하나 구현 후 코드가 덜 직관적이라는 단점이 있어 투 포인터로 문제를 풀이하였습니다.

• 무엇보다 투 포인터로 풀 생각을 하자마자 음수 및 양수에 대한 우려를 빠르게 해소할 수 있었습니다.(이분 탐색도 큰 문제는 없으나 체감상 바로 문제없음을 떠올렸습니다)

3. 정답 코드

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n;
    static int[] num;

    static void input() throws IOException{
        n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        num = new int[n];
        for(int i = 0;i < n; ++i) {
            num[i] = Integer.parseInt(st.nextToken());
        }
    }

    static void solution(){
        Arrays.sort(num);
        long answer = (long) 1e10;
        int[] ans = new int[3];
        for(int i = 0;i < n - 2; ++i) {
            int left = i + 1, right = n - 1;
            while(left < right) {
                long sum = (long)num[i] + num[left] + num[right];
                if(Math.abs(sum) < Math.abs(answer)) {
                    answer = sum;
                    ans[0] = num[i];
                    ans[1] = num[left];
                    ans[2] = num[right];
                }
                if(sum == 0) break;
                if(sum > 0) --right;
                else ++left;
            }
        }
        for(int i = 0;i < 3; ++i) {
            System.out.print(ans[i] + " ");
        }
    }

    public static void main(String[] args) throws IOException{
        input();
        solution();
    }
}

4. 추천 음악

떼굴떼굴 - Lucy
Link: https://www.youtube.com/watch?v=dNVLdO-qk_U

들으면서 코딩하면 한 문제 뚝딱입니다(물론 웬만해선 안 듣고 해야겠지만..ㅎ)