📢 백준 2018, 1940 문제에 이어서 투 포인터 알고리즘을 활용하는 세번째 문제입니다.
투 포인터 알고리즘에 대한 이해가 어려우시다면 아래의 문제들도 같이 풀어보시는 것을 추천합니다😃
[Java / 백준 2018] 수들의 합 5
[Java / 백준 1940] 주몽의 명령

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

❗ 문제를 읽고 헷갈릴 수 있는 부분

• 다른 두 수의 합으로 좋은 수를 찾는 것이기 때문에 합할 두 수와 좋은 수는 모두 다른 수이어야 한다!
• 수의 위치가 다르면 값이 같아도 다른 수로 취급한다!

ex)  0 2 5 3 6 3
A[0] + A[3] = A[3] 이므로 A[3]은 좋은 수 이다. (false)
A[0] + A[3] = A[5] 이므로 A[5]는 좋은 수 이다. (true)

분석

문제의 입력 예시가 너무 단순하여 직접 예시를 만들었고, 문제 해결 과정을 아래와 같이 단계적으로 진행했다.

1. 수의 개수 $N$을 입력받고 변수에 저장한다. N=10

2. $N$개의 수를 입력받아 배열 $A[N]$에 저장하고 오름차순 정렬한다.
   

3. 투 포인터 $i,j$를 배열 A의 양쪽 끝에 위치시키고, $i$와 $j$가 만날 때까지 포인터를 이동시키며 탐색한다.

4. 3단계의 과정을 배열의 모든 수에 대하여 반복하며 좋은 수가 몇 개인지 카운팅한다.

풀이 과정

📌 투 포인터 이동 방법

투 포인터 $i$,$j$를 배열 $A$의 양쪽 끝에 위치시키고, i와 j가 만날 때까지 포인터를 이동시킨다. 그리고 이 과정을 배열의 크기만큼 반복한다.

• $i$ : 가장 작은 수 인덱스
• $j$ : 가장 큰 수 인덱스
• $k$ : 좋은 수를 판별하기 위한 대상의 인덱스

• $A[i] + A[j] < A[k]$
  번호의 합이 A[k]보다 작으므로 작은 번호 인덱스를 올린다. $(i$++$)$
• $A[i] + A[j] > A[k]$
  번호의 합이 $A[k]$보다 크므로 큰 번호 인덱스를 내린다. $(j$--$)$
• $A[i] + A[j] = A[k]$
  $A[k]$가 좋은 수에 해당하므로 $count$를 증가시킨다. $(count$++$)$
  ❗ 이때, 해당 $A[k]$가 좋은 수임을 확인했으므로 더이상의 $A[i] + A[j] = A[k]$ 의 경우의 수를 찾을 필요는 없다. 따라서 더이상의 포인터 이동은 하지 않아도 된다.

k=3 일때 풀이 과정

• i = 0, j = 5
  $A[i]+A[j]=6 > A[k]$ 이므로 큰 값인 $j$를 감소시킨다.
  
• i = 0, j = 4
  $A[i]+A[j]=5 > A[k]$ 이므로 큰 값인 $j$를 감소시킨다. 단, $A[k]$와 $A[i],A[j]$는 모두 다른 수 이어야 하므로 $k$ 인덱스는 건너뛴다.
  
• i = 0, j = 2
  $A[i]+A[j]=3 = A[k]$ 이므로 A[3]이 좋은 수 이다. $count$를 증가시키고, 포인터 이동을 멈춘다.
  

위의 과정을 $k$가 배열 $A$의 모든 수에 대하여 반복하며 좋은 수가 몇 개인지 카운팅한다.

소스 코드

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()); // 수의 개수

        // N개의 수를 입력받아 배열 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 오름차순 정렬
        Arrays.sort(A);

        // 투 포인터 활용
        int count = 0;
        int i;
        int j;
        for(int k=0; k<N; k++) {
            i = 0;
            j = N-1;
            while(i<j) {
                if( i != k && j != k) {
                    if(A[i]+A[j] < A[k]) {
                        i++;
                    } else if (A[i]+A[j] > A[k]) {
                        j--;
                    } else { // A[i]+A[j] == A[k]
                        i++;
                        j--;
                        count++;
                        break;
                    }
                } else if (i == k) {
                    i++;
                } else if (j == k) {
                    j--;
                }
            }
        }
        
        // 결과 출력
        System.out.println(count);
        br.close();
    }
}

핵심 정리

이번 문제는 투 포인터 알고리즘을 이용하되, 추가적으로 생각해야할 옵션이 두 가지가 있었다.✌🏻

point 1. '좋은 수'에 해당하는 인덱스에는 '포인터'가 위치할 수 없다 !

사실 이 부분이 문제를 읽고 바로 파악할 수 없어서 힘들었다. 문제에 명시가 되어있었다면 더 좋았을 것 같다.🥺
이 부분을 해결하기 위해 $i$와 $j$가 모두 $k$와 다른 값일 때만 좋은 수 판별 연산 하도록 구현하였다.

if( i != k && j != k) {
	// 좋은 수 판별 연산
} else if (i == k) {
	i++;
} else if (j == k) {
	j--;
}

point 2. '좋은 수'임을 확인했다면, break를 사용하여 반복문을 나간다 !

결과 값 저장을 위한 count는 좋은 수가 몇 개인지를 확인하는 것이 목적이다. 따라서 반복문을 더이상 진행하지 않아도 된다! (사실 당연한 내용인데 혼자 헷갈려서 이 부분 놓치고 왜 틀렸는지 헤맸다..🤣)