투 포인터

투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.

 

[백준 2018번] 수들의 합 5

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

 

이 문제는 시간 복잡도 분석으로 사용할 알고리즘의 범위부터 줄여야 한다. 문제에 주어진 시간 제한은 2초인데 N의 최댓값은 10,000,000으로 매우 크게 잡혀 있다. 여기서 O(nlongn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야 한다. 이런 경우 자주 사용하는 방법이 투 포인터이다. 연속된 자연수의 합을 구하는 것이 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현하겠다.

 

시작 인덱스와 종료 인덱스를 투 포인터로 지정한다. start_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수에서 왼쪽 값을 삭제하는 것과 효과가 같으며 end_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수의 범위를 한 칸 더 확장한다는 의미이다. 같을 때는 경우의 수를 1 증가시키고 end_index를 오른쪽으로 이동시킨다. 

 

즉, 앞에서 배운 부분 배열의 합이
start_index가 ++되면 감소하고
end_index가 --되면 증가하는 것이다.

 

투 포인터 이동 원칙
- sum > N : sum = sum - start_index; start_index++;
- sum < N : end_index++; sum = sum + end_index;
- sum == N : count++; end_index++; sum = sum + end_index;

 

이를 end_index가 N이 될 때까지 반복하되, 포인터가 이동할 때마다 현재의 총합과 N을 비교해 값이 같으면 count를 1만큼 증가한다.

 

코드로 구현하면 다음과 같다.

 

[정답]

package algorithm;

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int start_index = 1;
        int end_index = 1;
        int count = 1;  // n이 15일 때 숫자 15만 뽑는 경우의 수
        int sum = 1;

        while(end_index != n) {
            if(sum < n) {   // 현재 연속 합이 n보다 작은 경우
                end_index++;
                sum += end_index;
            }
            else if(sum > n) {  // 현재 연속 합이 n보다 큰 경우
                sum -= start_index;
                start_index++;
            }
            else {      // 현재 연속 합이 n과 같은 경우
                count++;
                end_index++;
                sum+= end_index;
            }
        }
        System.out.println(count);
    }
}

 

---

 

[백준 1940번] 주몽

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

 

N의 최대 범위가 15,000이므로 O(nlogn) 시간 복잡도 알고리즘을 사용해도 문제가 없다. 일반적으로 정렬 알고리즘의 시간 복잡도는 O(nlogn)이므로 정렬을 사용해도 된다. 두 재료의 번호의 합, 즉 크기를 비교하므로 값을 정렬하면 해당 문제를 더 쉽게 풀 수 있다. 입력받은 N개의 재룟값을 정렬한 다음 양쪽 끝의 위치를 투 포인터로 지정해 문제에 접근한다.

투 포인터 이동 원칙
- A[i] + A[j] > M : j--;   // 번호의 합이 M보다 크므로 큰 번호 index를 내린다.
- A[i] + A[j] < M : i++;   // 번호의 합이 M보다 작으므로 작은 번호 index를 올린다.
- A[i] + A[j] == M : i++; j--; count++;   // 양쪽 포인터를 모두 이동시키고 count를 증가시킨다.

 

이를 i와 j가 만날 때까지 반복한다.

 

나는 두 포인터를 지정한 다음 2중 루프 대신 그냥 j 하나씩 이동시키고 끝에 다다르면 i 값 하나 증가시킨 후 j = i + 1 로 만들어 완전 탐색식으로 풀었다. 이중 루프를 만들진 않아서 통과는 했지만 로직적으로는 해당 방법이 더 알맞은 것 같다.

 

[정답]

package algorithm;

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);   // 정렬
        
        int count = 0;
        int i = 0, j = n - 1;
        while(i < j) {  // 투 포인터 이동 원칙 따라 포인터 이동하며 처리
            if(arr[i] + arr[j] < m)
                i++;
            else if(arr[i] + arr[j] > m)
                j--;
            else {
                count++;
                i++; j--;
            }
        }
        System.out.println(count);
    }
}

 

[원본]

package algorithm;

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int count = 0;
        int i = 0, j = 1;
        while(i != n-1) {
            if(arr[i] + arr[j] == m) {
                count++;
            }
            j++;
            if(j == n) {
                i++;
                j = i + 1;
            }
        }
        System.out.println(count);
    }
}

 

---

 

[백준 1253번] 좋다

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

 

N의 최대 개수가 2,000이지만 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N^2보다 작아야 한다. 만약 시간 복잡도가 N^2인 알고리즘을 사용하면 최종 시간 복잡도는 N^3이 되어 제한 시간 안에 문제를 풀 수 없기 때문이다. 따라서 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 최소 O(nlogn)이어야 한다. 

 

판별이 되는 수를 K라 가정했을 때 투 포인터 i, j를 배열 A 양쪽 끝에 위치시키고 다음 조건에 따라 탐색을 수행한다.

투 포인터 이동 원칙
- A[i] + A[j] > K : j--;
- A[i] + A[j] < K : i++;
- A[i] + A[j] == K : i++; j--; count++;

 

이를 K가 N이 될 때까지 반복하며 좋은 수가 몇 개인지 센다.

 

[정답]

package algorithm;

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int result = 0;
        long[] A = new long[n];
        for (int i = 0; i < n; i++) {
            A[i] = sc.nextLong();
        }
        Arrays.sort(A);

        for(int k = 0; k < n; k++) {
            long find = A[k];
            int i = 0;
            int j = n - 1;
            // 투 포인터 알고리즘
            while(i < j) {
                if(A[i] + A[j] == find) {
                    // find는 서로 다른 두 수의 합이어야 함을 체크
                    if(i != k && j != k) {
                        result++;
                        break;
                    }
                    else if(i == k) {   // 서로 다른 두 수는 해당 수를 이용해서 만들어지면 안된다.
                        i++;            // 해당 값 벗어나기.
                    }
                    else if(j == k) {   // 마찬가지. 포인터 변경 및 계속 수행하기.
                        j--;            // 해당 값 벗어나기.
                    }
                }
                else if(A[i] + A[j] > find) j--;
                else i++;
            }
        }
        System.out.println(result);
    }
}

 

투 포인터에서 목표는 두 개의 포인터로 값을 증가, 감소시키며 관찰하는 것이기 때문에 하나의 포인터는 하나의 역할만 해야 한다. 

 

 

 

 

[참고자료]

- Do it! 알고리즘 코딩 테스트 자바편

- https://silver-lemon-candy.tistory.com/6

백준 1253: 좋다 [골드 Ⅳ / Java]