[JAVA] 자바 #4 - 투 포인터

☘️ 투 포인터란?

• 연속되는 value들을 이용하여 특정 목표에 맞는 값을 찾아주는 알고리즘이다.
• 연속된 값들을 이용하여 풀어나가는 문제에 한정적으로 사용해야 한다.
• 주어진 값들의 연속성이 선행조건으로 주어지지 않는 경우에는 투포인터를 사용할 수 없다.
• 문제에서 주어진 값들을 그대로 활용해야 하는 경우나 정렬을 통하여 연속성을 추가해줄 수 있는 경우에 사용할 수 있는 알고리즘

---

🌿 투 포인터가 필요한 이유

• 정수로 이루어진 배열이 있다고 가정
• 그 정수들중 연속된 몇 개의 정수들의 합이 특정 값이 된다고 하였을 때 그 값을 만들 수 있는 조합은 몇 가지가 될 것이냐라는 문제가 있다고 한다.
• 만일 투 포인터를 사용하지 않는다면 백트레킹 등을 이용하여 나올 수 있는 모든 케이스에 대해 탐색하는 것이 최선
• 문제를 출제하는 사람은 투 포인터를 생각하고 문제를 출제하였을 것이기 때문에 필연적으로 시간 초과가 발생할 것
• 투 포인터 사용 시 시간 복잡도를 줄일 수 있다.

---

🌱 투 포인터를 이용한 문제 풀이 방법

• 투 포인터는 우선 배열을 가르키는 두 개의 포인터를 만든다.
  • 두 개의 포인터는 각각 배열에서 특정 위치를 지정해주는 시작점과 끝점이라고 할 수 있다.(start pointer와 end pointer)
• 그 포인터를 이동시켜가면서 우리가 원하는 값을 찾는다.
• 배열내 연속된 숫자들의 합을 이용하는 것이므로 더해가면서 값을 찾아주어야 한다. 두 개의 포인터를 정수들을 더해주는 과정에서 움직이게 된다.
  • 최초에는 어떠한 값도 합에 들어오지 않았기 때문에 end pointer를 이동시켜 첫 번째 값을 포함시킨다.
  • 이때 우리가 원하는 값이 나왔다면 답을 계산해줄 count 변수에 하나의 값을 더해주고 그렇지 않은 경우라면 조건에 따라 start pointer와 end pointer를 이동시켜준다.
  • end pointer는 현재 포함된 값들의 합이 원하는 값보다 작은 경우에 이동시켜준다. 현재까지 등장한 숫자들로는 원하는 값을 만들 수 없었기 때문
  • start pointer는 우리가 원하는 값을 찾았거나 그보다 값이 큰 경우에 이동시켜주는데 이는 현재까지 등장했던 숫자들을 이용하여 원하는 값을 찾은 이상 지금까지 포함된 숫자들에 새로운 숫자들을 더해서는 원하는 값을 찾을 수 없다는 가정이 포함되어있기 때문

---

🍃 백준 2018) 수들의 합 5

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

---

• 입력 : 첫 줄에 정수 N이 주어진다.
• 출력 : 입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오
• 문제 분석
  • 문제에 주어진 시간 제한은 2초, N의 최댓값은 10,000,000
    • 이 문제는 시간 복잡도 분석으로 사용할 알고리즘의 범위부터 줄여야 한다.
  • O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n)의 시간 복잡도 알고리즘 사용 : 투 포인터
  • 연속된 자연수의 합을 구하는 것이 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수 표현할 예정
  • 투 포인터 이동 원칙
    • sum > N : sum - start_index; start_index++;
    • sum < N : end_index++; sum = sum + end_index;
    • sum == N : end_index++; sum = sum + end_index; count++;

문제 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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 count = 1, start_index = 1, end_index = 1, sum = 1;

        while (end_index != N) {
            if (sum == N) {
                count++;
                end_index++;
                sum += end_index;
            } else if (sum > N) {
                sum -= start_index;
                start_index++;
            } else {
                end_index++;
                sum += end_index;
            }
        }
        System.out.println(count);
    }
}

---

🌳 백준 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보다 작거나 같은 자연수이다.
• 출력 : 첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.
• 문제 분석
  • 두 재료의 번호의 합, 즉 크기를 비교하므로 값을 정렬하면 문제를 좀 더 쉽게 풀 수 있다.
  • N의 최대 범위가 15,000이므로 O(nlogn) 시간 복잡도 알고리즘 사용해도 문제는 없다. (일반적으로 정렬 알고리즘의 시간 복잡도는 O(nlogn)이다. 즉 정렬을 사용해도 괜찮음)
  • 입력받은 N개의 재룟값을 정렬한 다음 양쪽 끝의 위치를 투 포인터로 지정해 문제에 접근
  • 풀이 과정
    • 재료 데이터fmf 배열 A[N]에 저장한 후 오름차순 정렬
    • 투 포인터 i,j를 양쪽 끝에 위치시킨 후 문제의 조건에 적합한 포인터 이동 원칙을 확용해 수행
      • 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를 증가시킨다.

문제 풀이 코드

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

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 M = Integer.parseInt(br.readLine());
        int[] A = new int[N];

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

        Arrays.sort(A);

        int count = 0;
        int i = 0;  //A[0] -> Min
        int j = N - 1;    //A[N-1]
        while (i < j) {
            if (A[i] + A[j] < M) 
                i++;
            else if (A[i] + A[j] > M) 
                j--;
            else {
                count++;
                i++;
                j--;
            }
        }
        System.out.println(count);
    }
}