2470번

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

2470번: 두 용액

오늘 풀은 문제는 투 포인터 문제이다.

골드 5라는 등급을 받고 있는 문제이지만 조건만 잘 정한다면 금방 풀 수 있는 문제인 것 같다.

나는 이 문제를 처음에는 이분탐색트리를 사용해서 풀려고 했었다. 하지만 메모리 초과로 풀 수 없었다...

이번 문제를 풀면서 메모리 초과와 시간초과에 대해서 공부해야 겠다고 생각하는 계기였다..

 

그래서 먼저 이 문제의 접근 방식은 처음과 끝에서 투포인터를 이용하는 방식으로 탐색을 진행하면서 조건에 맞추어 처리하는 방식이다.

 

여기서 고려해야할 것은 두 값의 합이 0보다 크거나 같은 경우와 0보다 작은 경우다.

만약 합이 0보다 크거나 같다면 끝 부분의 포인터를 앞쪽(시작지점 방향)으로 움직인다.

만약 합이 0보다 작다면 시작지점의 포인터를 끝지점 방향으로 움직인다.

 

이렇게 두개의 포인터를 움직이는 과정에서 절댓값이 작은 값을 계속하여 갱신한다.

이 과정을 끝지점에 있던 포인터와 시작지점에 있던 포인터가 만나면 탐색을 중지한다.

 

나는 이 과정에서 작은 값을 갱신하지 않고 트리셋을 이용하여 최대최소를 꺼내어 비교하였는데 크기가 작은 예제들은 오답없이 출력되었지만, 정답 제출시에는 크기가 큰 값들이 들어와서 트리에 너무 많은 값을 저장하여 메모리 초과로 오답처리 되었다.

그래서 이 트리부분을 단순 int값으로 바꾸었다. 그래서 int값을 갱신해주는 방식으로 변환하여 해결했다.

 

정답 코드는 아래와 같다.

package backjoon.b2470;

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

public class b2470 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];

        for(int i=0; i<n; i++){
            arr[i]= Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);
        int left=0;
        int right=n-1;
        int minAl = 0;
        int minSan = 0;
        int minSum = Integer.MAX_VALUE;
        while (left<right){
            int sum = arr[left]+arr[right];
            if(sum>=0){
//                plusAndZero.add(new Node(arr[left],arr[right]));
                if(Math.abs(sum)<Math.abs(minSum)){
                    minSum = sum;
                    minAl = arr[left];
                    minSan = arr[right];
                }
                right--;
            } else {
//                minus.add(new Node(arr[left],arr[right]));
                if(Math.abs(sum)<Math.abs(minSum)){
                    minSum = sum;
                    minAl = arr[left];
                    minSan = arr[right];
                }
                left++;
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(minAl).append(" ").append(minSan);
        System.out.println(sb);
    }
}