자바 - 백준 2473 / 세 용액

백준 2473 / 세 용액
골드3

구현 방법

N개의 용액중에 3개를 선택하여 0에 가장 가까운 세 용액을 출력해야 한다.

N의 범위는 최대 5000이기 때문에 완전 탐색하면 시간 초과가 난다.

자연스럽게 시간복잡도를 줄일 방법을 찾을 텐데 떠오르는 알고리즘이 이분탐색과 투포인터 두개 였다.

 

이분탐색

이분탐색으로 구현할 경우, 처음과 끝을 기준으로 가운데 탐색을 지속적으로 한다.

이러면 두 용액을 고정시켜 놓고 나머지 한 용액을 이분탐색으로 정하는 방식으로 구현 해야한다.

이러면 시간복잡도가 O(n^2 * longn)이 된다.

 

투포인터

투포인터로 구현할 경우, 두 포인트가 움직이면서 범위를 조정한다. 

자 그러면 한 용액만 고정시켜놓고 구현이 가능해진다

이러면 시간복잡도가 O(n * n)으로 이분탐색보다 빠르다.

코드

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

/**
 * 백준 2473
 * 세 용액
 * 골드3
 * https://www.acmicpc.net/problem/2473
 */
public class Boj2473 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        long[] answer = new long[3];

        int N = Integer.parseInt(br.readLine());
        List<Long> nums = new ArrayList<>();

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

        Collections.sort(nums);

        long near = 3000000001L;

        for(int i = 0; i < N; i++) {
            long cur = nums.get(i);

            int start = i + 1;
            int end = N - 1;

            while(start < end) {
                long sum = cur + nums.get(start) + nums.get(end);
                int mid = start + ((end - start) / 2);

                if (Math.abs(sum) < Math.abs(near)) {
                    near = sum;
                    answer[0] = cur;
                    answer[1] = nums.get(start);
                    answer[2] = nums.get(end);
                }

                if(sum > 0)
                    end--;
                else
                    start++;
            }
        }

        System.out.println(answer[0] + " " + answer[1] + " " + answer[2]);
    }
}

 

느낀점

1년전 고군분투 하다 다음을 기약하며 넘겼던 문제였는데, 의외로 쉽게 풀렸다.

나 성장한걸지도?