[BOJ_2470] 두 용액

설명

---

어짜피 두개만 선택하는 경우의 수이고 이것을 모두 비교하면서 진행하는 백 트레킹 방식을 진행하기에는 100000C2 50억이므로 불가능 그래서 투포인터 방식을 사용해서 진행하는데 이때, 오름 차순으로 정렬 후 선택하게 되면 결국 앞에서 나가는 것은 무조건 음수에서 양수로 나아가는 방식이고 이를 토대로 start, end 조건을 걸어서 풀면 된다. 

 

 

코드

---

package two_pointer;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_2470 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");
        int N = Integer.parseInt(tk.nextToken());
        tk = new StringTokenizer(in.readLine()," ");
        List<Integer> list = new ArrayList<>();

        for(int i = 0; i < N; i++){
            list.add(Integer.parseInt(tk.nextToken()));
        }
        Collections.sort(list); //오름 차순 정렬

        int start = 0;
        int end = N - 1;
        int ans_start = 0;
        int ans_end = 0;
        int min = Integer.MAX_VALUE;
        while (start < end){
            //0보다 작으면 start 상승시켜서 다음 수로 비교해보면 됨
            if(list.get(start) + list.get(end) < 0){
                if(Math.abs(list.get(start) + list.get(end)) < Math.abs(min)){
                    ans_start = start;
                    ans_end = end;
                    min = list.get(start) + list.get(end);
                }
                start++;
            } else if (list.get(start) + list.get(end) > 0) {
                if(Math.abs(list.get(start) + list.get(end)) < Math.abs(min)){
                    ans_start = start;
                    ans_end = end;
                    min = list.get(start) + list.get(end);
                }
                end--;
            }else{
                ans_start = start;
                ans_end = end;
                break;
            }
        }
        System.out.println(list.get(ans_start) + " " + list.get(ans_end));
    }
}

2470번: 두 용액