📢 백준 2018 문제에 이어서 투 포인터 알고리즘을 활용하는 두번째 문제입니다.
[Java / 백준 2018] 수들의 합 5

문제

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

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

분석

재료의 개수 N 그리고 N개의 재료들의 고유번호가 있을때, 2가지의 재료의 합이 M이 되면 갑옷을 만들 수 있다.
2개의 고유번호를 합한 값이 M이 되는 경우의 수를 구해야 한다. 작성할 코드를 단계별로 생각해 보자.

1. 재료의 개수$(N)$, 갑옷이 완성되는 번호의 합$(M)$을 입력받고 각 변수에 저장한다.
   N=6, M=9
2. 재료들의 고유번호를 배열 $A[N]$에 저장하고 오름차순 정렬한다.
   
3. 투 포인터 $i,j$를 각각 제일 작은 수와 제일 큰 수에 위치시킨다. 즉, 양쪽 끝에 위치시키고 $i$와 $j$가 만날 때까지 포인터를 이동시키며 탐색한다.

풀이 과정

📌 투 포인터 이동 방법
투 포인터 i,j를 각각 최소값과 최대값의 인덱스에 위치시킨다.
$i$ : 작은 번호 인덱스
$j$ : 큰 번호 인덱스

• $A[i] + A[j] < M$ 인 경우, 번호의 합이 $M$보다 작으므로 작은 번호 인덱스를 올린다. $(i$++$)$
• $A[i] + A[j] > M$ 인 경우, 번호의 합이 $M$보다 크므로 큰 번호 인덱스를 내린다. $(j$--$)$
• $A[i] + A[j] = M$ 인 경우, 번호의 합이 $M$과 같으므로 양쪽 포인터 모두 이동시키고 $count$를 증가시킨다. $(i$++, $j$--, $count$++$)$

양쪽 끝에 위치한 두 개의 포인터가 만날 때까지 포인터를 이동시키면서 연산을 반복한다.
M = 9

• i = 0, j = 5
  $A[0]+A[5]=8 < M$ 이고, $j$는 이미 최대값에 위치하므로 더이상 큰 값으로 이동할 수 없다. 따라서 합계의 크기를 키우기 위해 최소값에 위치한 $i$를 증가시킨다.
  

• i = 1, j = 5
  $A[1]+A[5]=9=M$ 이므로, $count$를 증가시키고 양쪽 포인터를 모두 이동시킨다. 수학적으로 계산해보면 두 개의 포인터 중 하나만 이동시킨다고 해도 합이 $M$이 되는 경우를 찾을 수 없다.
  

• i = 2, j = 4
  $A[2]+A[4]=8<M$ 이므로, 작은 수에 위치한 $i$를 증가시킨다.
  

• i = 3, j = 4
  $A[3]+A[4]=9=M$ 이므로, $count$를 증가시키고 포인터가 만나서 더이상 이동할 수 없으므로 반복문을 종료한다.
  

소스코드

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

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());	// 갑옷이 완성되는 번호의 합

        // 재료들의 고유번호를 입력받아 배열 A[N]에 저장한다.
        int[] A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        // A[N]을 오름차순 정렬한다.
        Arrays.sort(A);

        int count = 0;	// 갑옷을 만들 수 있는 경우의 수
        int i = 0;		// min 값이 저장된 인덱스
        int j = N-1; 	// max 값이 저장된 인덱스

        // 투 포인터 이동 원칙을 이용해 탐색
        while(i < j) {
            if(A[i]+A[j] < M) {
                i++;
            } else if (A[i]+A[j] > M) {
                j--;
            } else { // A[i]+A[j] == M
                count++;
                i++;
                j--;
            }
        }

        // 결과 출력
        System.out.println(count);
        br.close();
    }
}

핵심 정리

point 1. 탐색할 데이터들을 오름차순 정렬하자 !

문제를 분석하는 과정에서 처음에는 입력받은 데이터를 그대로 둔 상태에서 투 포인터를 사용하려 했지만, 포인터를 위치시킬 인덱스와 이동 방향을 계획하기가 어려웠다.🤔 결국 투 포인터를 학습한 기본 문제처럼 오름차순으로 정렬한 후 문제에 다시 접근하였다.

• 오름차순 정렬

Arrays.sort(arr);

• 내림차순 정렬

Arrays.sort(arr, Collections.reverseOrder());

point 2. 투 포인터를 양쪽 끝에 위치시킨다 !

투 포인터 알고리즘을 사용해서 문제를 풀이하는 방법은 두 가지가 있다.

• 포인터 2개가 처음부터 같은 방향으로 진행해 나가는 방법
• 포인터 2개가 양끝에서 반대로 진행해나가는 방법

문제를 분석하면서 두 방법 중 더 효율적인 방법을 선택하고 풀이하는 능력을 키우면 문제 해결 속도가 더 빨라질 것 같다.😝