[알고리즘]백준 2467: 용액

 

해결방법

2개의 용액을 골라야한다. 일반적으로 조합을 구하기 위해서는 O(2^N)의 시간복잡도를 가진다. 위 문제의 경우 2≤N≤100000이므로 적용불가능하다. (대략 N이 10을 넘어가면 불가능)

투포인터로 접근한다.

left+right의 절댓값이 answer보다 작다면 answer 갱신(left와 right 위치 저장)

1. left와 right의 용액을 더했을 때 양수이면 → right-1
2. left와 right의 용액을 더했을 때 음수이면 → left+1

left<right을 만족할 때까지 위 과정을 반복

결론적으로 투포인터로 O(N)의 시간복잡도로 문제를 해결할 수 있다.

 

 

코드

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

// 308ms, 투포인터, O(N)
public class Main_2467_G5_용액_투포인터 {
    static int N;
    static int[] liquid;

    public static void main(String[] args) throws IOException{
        // 1. 입력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        // 2. 투 포인터
        long answer = Long.MAX_VALUE;
        int answerLeft = 0;
        int answerRight = 0;
        int left = 0;
        int right = N-1;
        while(left<right){
            long s = (long)liquid[left]+(long)liquid[right];
            if(Math.abs(s)<=answer){
                answer = Math.abs(s);
                answerLeft = left;
                answerRight = right;
            }
            if(s>0) right--;
            if(s<=0) left++;
        }

        // 3. 출력
        System.out.printf("%d %d", liquid[answerLeft], liquid[answerRight]);
    }
}

 

링크

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