백준 2467 자바 - 용액 (BOJ 2467 JAVA)

문제 : boj2467

 

1.

  당연히 모든 쌍을 확인해보면 O(N^2)이 걸릴 것이므로 통과가 불가하다. 이 문제는 투 포인터 알고리즘으로 풀 수 있는 기본형 문제이다. 또는 안풀어보긴 했으나 이분탐색으로도 문제없이 풀 수 있을 것 같다(N개를 TreeSet에 넣어둔 후 N개의 값을 순회하며 해당 값에 -1을 곱한 값에 대해 TreeSet에서 ceilling과 floor를 확인해 그 중 작은 수를 택하면 될 듯함).

 

2.

  이미 정렬되어 들어온 데이터 이므로 정렬과정 필요 없이 첫번째 값을 s로 가르키고, 맨 뒤의 값을 e로 가르켜보자.

이제 s와 e가 가르키는 값을 합쳐가며 이 중 0과 가장 가까운 값을 찾으면 된다. s와 e를 변경하는 규칙은 다음과 같다.

 

arr[s]+arr[e] == 0 -> 바로 출력

arr[s]+arr[e] < 0 -> 0으로 더 가까이 가기위해서는 e를 늘리거나, s를 늘려야 한다. 하지만 e의 시작점이 이미 맨 끝에서 시작한 것이므로 s를 증가시키면 된다.

arr[s]+arr[e] > 0 -> 마찬가지로 e를 줄이거나 s를 줄여야 0으로 가까워진다. 역시 마찬가지로 s가 이미 맨 처음에서 시작했으므로 e를 줄이면 된다.

 

혹시 s의 증감과 e의 증감을 반대로 하고싶다면 처음에 정중앙에서 s와 e를 시작하면 된다.

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());

        int s = 0, e = n-1;
        int min = Integer.MAX_VALUE;
        int ansS = 0, ansE = 0;
        while (s < e) {
            int sum = Math.abs(arr[e]+arr[s]);
            if (sum < min) {
                min = sum;
                ansS = s;
                ansE = e;
            }
            if (sum == 0)
                break;

            if (arr[e]+arr[s] > 0) e--;
            else s++;
        }

        System.out.println(arr[ansS] + " " + arr[ansE]);
    }

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