백준 2467 JAVA : 용액

문제

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

2467번: 용액

 

풀이 예상

투포인터를 이용한 풀이

 

풀이방법 (접근 방법 & 시간복잡도)

1. startPoint = 0, endPoint = N-1 에 두고 시작한다.

2. 합의 절댓값이 diff보다 작다면 answer에 해당지점을 갱신한다.  

3. nums[startPoint] + nums[endPoint] 가 0보다 작다면 startPoint를 증가시키고 아니라면 endPoint를 감소시킨다.

 

시간복잡도 => O(N)

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

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] nums = new int[N];

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

        int startPoint = 0;
        int endPoint = N-1;

        int diff = Integer.MAX_VALUE;
        int answer1 = 0;
        int answer2 = N-1;

        while(startPoint < endPoint) {
            int sum = nums[startPoint] + nums[endPoint];

            if(Math.abs(sum) < diff) {
                answer1 = startPoint;
                answer2 = endPoint;
                diff = Math.abs(sum);
            }
            if(sum < 0) {
                startPoint++;
            }else {
                endPoint--;
            }
        }

        System.out.println(nums[answer1] +" "+nums[answer2]);

    }
}

 

결과