자바(백준) 2470 두 용액

오답 노트 & 새로 알게 된 점

이 문제를 보고 내가 나중에 이걸 보고 투 포인터를 사용할 수 있을까라는 생각이 들었다.

 

제일 처음에 드는 생각은 당연히 O(N^2)일 것이다.

숫자 하나를 선택하고 나머지 숫자들을 다 더해보고 절댓값이 가장 작은 값을 고르는 방법이다.

하지만 N이 100,000이기 때문에 TLE가 바로 난다. 

그렇다면 여기서 우리는 어떤 방법을 사용해야 시간 복잡도를 줄일 수 있을까?

 

배열들을 정렬하고 최소값과 최대값을 더해보자.

더한 값이 양수라면, 최대 입장에서는 최소값을 더해도 양수가 나온다면, 나머지 값들은 당연히 계산을 안해도 양수가 나올 것이다. 따라서 e를 하나 줄여준다.

더한 값이 음수라면, 최소 입장에서는 최대값을 더해도 음수가 나오니까 나머지 값들은 계산을 안해도 당연히 음수가 나온다. 그래서 s를 하나 늘린다. -> 현재 수에서는 계산할 필요가 없기 때문이다.

 

그렇다면 시간 복잡도는

정렬 -> O(NlogN)

이동 -> O(N)으로

총 O(NlogN)으로 TLE가 나지 않는다.

 

---

 

코드

package TwoPointers;
 
import java.io.*;
import java.util.*;
 
public class BOJ2470 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N;
    static int A[];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = atoi(br.readLine());
 
        A = new int[N];
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        for (int i = 0; i < N; i++) {
            A[i] = atoi(st.nextToken());
        }
 
        Arrays.sort(A);
 
        pro();
    }
 
    static void pro() {
        int s = 0, e = N - 1, s1 = 0, s2 = 0;
        int ans = Integer.MAX_VALUE;
        //s < e인 이유는 똑같은 용액 합치기 X
        while (s < e) {
            int sum = A[s] + A[e];
 
            if(ans > Math.abs(sum)){
                s1 = s;
                s2 = e;
                ans = Math.abs(sum);
            }
 
            if(sum > 0) e--;
            else s++;
        }
 
        System.out.println(A[s1] + " " + A[s2]);
    }
}