[투 포인터] 백준 2467. 용액 / 백준 14921. 용액 합성하기

투포인터(Two-Pointer)

두개의 포인터를 활용해 특정 조건을 만족하는 부분구간을 찾는 알고리즘이다.

일반적으로는 정렬된 배열에 대해서 수행한다. 반복문 두개를 활용해 탐색하지 않고, 선형 반복문 1개만 사용하므로 O(N)의 시간복잡도를 갖는다.

 

알고리즘 구현 방법

1. 배열의 특정위치에서 두개의 포인터를 셋팅한다(start, end)

2. 두 포인터 사이의 구간을 보고 조건을 만족하는지 확인한다.

3. 조건을 찾을때 까지 반복한다.

 

cf) 이때 두 포인터 사이의 간격이 일정하게 유지되면 슬라이딩윈도우이다.

 

백준 2467. 용액

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

두 수의 합이 0에 가까운 집합을 구하는 문제이므로, 투포인터 또는 이진탐색을 활용할 수 있다.

직관적으로 투포인터로 풀어보았다.

 

cf)

공간복잡도 : 배열(O(N)) + 결과(O(1)) => O(N)

시간복잡도 : 배열(O(N)) + 입력(O(N)) + 투포인터(O(N)) => O(N)

 

풀이

1. 0과 n-1을 각 포인터로 지정한다(start, end)

2. 투포인터를 사용하여 합이 0에 가까운 구간을 탐색한다

    2-1. min > Math.abs(arr[start]+arr[end]) 즉 두수의 합이 현재 가장 작은 합보다 작으면 저장한다.

    2-2. arr[start]+arr[end] > 0 즉 두수의 합이 0보다 크면 더 줄여야하므로 end--;

    2-3. arr[start]+arr[end] < 0 즉 두 수의 합이 0보다 작으면 더 커져야 하므로 start++;

 

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());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) arr[i] = Integer.parseInt(st.nextToken());
        int left=0, right=N-1, min=Integer.MAX_VALUE;
        int[] resultArr = new int[2];
        //투포인터
        while(left<right) {
            int sum = arr[left]+arr[right];
            if(Math.abs(sum) < min) {
                min = Math.abs(sum);
                resultArr[0] = arr[left];
                resultArr[1] = arr[right];
            }
            if(sum > 0) right--;
            else if(sum < 0) left++;
            else { //0 나오면 바로 종료
                resultArr[0] = arr[left];
                resultArr[1] = arr[right];
                break;
            }
        }
        System.out.println(resultArr[0]+" "+resultArr[1]);
    }
}

 

 

백준 14921. 용액 합성하기

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

마찬가지로 투포인터로 푼다. 풀이도 같다.

 

풀이

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());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int min = Integer.MAX_VALUE, value = 0, left = 0, right = N-1;
        while(left < right) {
            int sum = arr[left]+arr[right];
            if(sum<0) left++;
            else right--;

            if(min > Math.abs(sum)) {
                min = Math.abs(sum);
                value = sum;
                if(min == 0) break;
            }
        }

        System.out.println(value);
    }
}