[알고리즘] 투 포인터(Two Pointer)

1. 투 포인터 알고리즘이란

리스트나 배열에 순차적으로 접근하여 두 개의 포인터를 가지고 목표로 하는 값을 찾아내는 알고리즘
O(n)의 시간 복잡도를 가진다.

참고 : https://butter-shower.tistory.com/226

 

 

2. 문제를 보면서 알고리즘을 살펴보자.

1940번: 주몽

문제

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

예제 입력 

6
9
2 7 4 1 5 3

예제 출력

2

 

투 포인터 알고리즘 원리

* 배열 혹은 리스트의 양쪽 끝을 포인터로 잡아 사용하기 위해서 오름차순으로 정렬이 된 상태여야 한다.

 

1. 오름차순으로 정렬

• 위의 문제에서 2 7 4 1 5 3 으로 들어온 입력 값을 오름차순으로 정렬하여 1 2 3 4 5 7로 먼저 만들어준다.
• 양쪽 끝을 각각 포인터(startIdx, endIdx)로 잡아 문제를 해결할 것이다.

 

2. 포인터의 값을 더한 후 움직일 포인터를 판단한다.

• 갑옷이 만들어 질 수 있는 숫자인 9인데 1과 7을 더한 값은 8로 더 작다.
• 따라서 우리는 더 큰 값이 필요하다. startIdx를 증가시켜준다.
  • 두 포인터의 값의 합계가 9보다 큰 경우, 더 작은 값이 필요하므로 endIdx를 감소시켜준다.

 

3. 우리가 원하는 값과 같은 값을 얻으면 포인터를 둘다 증가/감소 시켜준다.

• 2와 7을 더하면 9로 갑옷을 해당 재료들로 우리는 갑옷을 만들 수 있다.
• 우리가 미리 오름차순으로 정렬을 해두었기 때문에 M과 동일한 값을 얻은 경우 해당 포인터에서 한쪽만 움직이는 것은 의미가 없다.
• startIdx를 그대로 두고 endIdx를 감소시켜봤자 우리가 원하는 값보다 작은 값만 나올테고
• endIdx를 그대로 두고 startIdx를 증가시켜봤자 우리가 원하는 값보다 큰 값만 나올 것이다.
• 따라서 두 포인터 모두 증가/감소를 시켜준다.

 

4. startIdx가 endIdx보다 작은 동안 2 ~ 3을 반복한다. 

 

알고리즘 문제 풀이

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

public class Main {

    private static int N; // 재료의 개수
    private static int M; // 갑옷을 만드는데 필요한 재료의 수
    private static int[] nums;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

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

        System.out.println(solution());

    }

    private static int solution() {
        int count = 0;
        int startIdx = 0;
        int endIdx = N -1;

        // 시작 전 오름차순 정렬이 된 상태이어야 함.
        Arrays.sort(nums);

        while (startIdx < endIdx) {
            int sum = nums[startIdx] + nums[endIdx];

            if (sum > M) endIdx--;
            else if(sum < M) startIdx++;
            else {
                count++;
                startIdx++;
                endIdx--;
            }
        }
        return count;
    }
}