[백준] 두 용액 2470 java - 투 포인터

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

 

 

첫번째 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        long[] water = new long[N];

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

        Arrays.sort(water);

        int index = 0;
        for(int i=0;i<N;i++){
            if(water[i]<0&&water[i+1]>=0) {
                index = i;
                break;
            }
        }

        long min = Integer.MAX_VALUE;
        long minVal1 = 0;
        long minVal2 = 0;

        for(int i=0;i<=index;i++){
            long start = water[i];
            for(int j=index+1;j<N;j++){
                long end = water[j];
                min = Math.min(min, Math.abs(start+end));
                if(min==Math.abs(start+end)){
                    minVal1 = start;
                    minVal2 = end;
                }
            }
        }
        System.out.println(minVal1+" "+minVal2);

    }

}

이중 반복문을 사용해서

당연히 시간 초과가 발생할 수 밖에,,,

 

 

두 번째 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        long[] water = new long[N];

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

        Arrays.sort(water);

       // -99 -2 -1 4 98

        long min = 2000000000;
        long minVal1 = 0;
        long minVal2 = 0;
        int start = 0;
        int end = N-1;

        while(start<end){
            long sum = water[start]+water[end];
            min = Math.min(min, Math.abs(sum));

            if(min==Math.abs(sum)){
                minVal1 = water[start];
                minVal2 = water[end];
            }

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

        System.out.println(minVal1+" "+minVal2);

    }

}

원래는 이분 탐색을 이용해서 풀려고 했지만

최소값, 최대값의 범위를 설정하는게 어려워서

투 포인터를 사용했다 !!