[BOJ 2470] 두 용액 (Java, 투 포인터)

 

 

 

---

문제 링크

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

2470번: 두 용액

---

풀이

- 투 포인터로 문제 풀이 (이진탐색으로 풀이 가능하나 개념적으로 조금 어려움)

- 두 용액을 더 했을 때 0에 가까운 두 수를 구하는 문제 

- 양 끝에서 투 포인터를 시작해서 서로를 향해 이동

- sum 의 값이 양수인 경우 R을 감소, 음수인 경우 L을 증가

0	1	2	3	4
-99	-2	-1	4	98

 

-99, 98 = -1 이므로 L증가 

-2, 98 = 97 이므로 R 감소 

-2, 4 = 2 이므로 R감소

-2,-1 = -3이므로 L증가 (종료)

 

시간 복잡도

- 오름차순 정렬 수행 : O(NlogN)

- 투 포인터 탐색 : O(N)만큼 수행 

고로 O(NlogN)만큼 걸림

 

---

제출 코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();

    static int N;
    static int[] liquid;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        liquid = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            liquid[i] = Integer.parseInt(st.nextToken());
        }
    }

    static void pro() {
        Arrays.sort(liquid);

        int L = 0, R = N - 1, bestValue = Integer.MAX_VALUE;
        int v1 = 0, v2 = 0;
        while(L < R) {
            int sum = liquid[L] + liquid[R];
            if(bestValue > Math.abs(sum)) {
                bestValue = Math.abs(sum);
                v1 = liquid[L];
                v2 = liquid[R];
            }
            
            if(sum > 0) R -= 1;
            else L += 1;
        }

        sb.append(v1).append(" ").append(v2);
        System.out.println(sb);
    }

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

 

보통 배열 연산시 0번 인덱스를 비우고 시작하는게 좀 더 알아보기 좋으니, 의식해서 초기화하고 처리할 수 있도록 해야겠다 !