• 두 수의 합 문제의 경우 좋다와는 달리 A = B + C에서 A가 1개로 정해져 있으므로, 알고리즘은 비슷하고 단지 left와 right을 left > right 될 때 까지 while문을 돌려주면 된다.

문제 이해

숫자 배열이 존재한다.
이 때, 숫자 배열에서 원소 A,B,C를 선택하자.(A,B,C의 index는 모두 다르다)
만약, A = B + C라면, A는 좋은 수이다.

이 때, 좋은 수의 개수를 구하라.

• 1 8 9 9의 경우, 9가 중복되었지만 다른 위치에 나와있으므로 좋은수가 2개 존재하는 것으로 생각한다.

문제 풀이

여기서 주목한 점은 "더하기"를 한다는 것이다.
예전에 풀었던 문제 중 A + B = C를 활용하는 방법이 있었다.
정확히는 A는 증가만 하는 값이고, B는 감소만 하는 값이라면, C를 증가시키기 위해서는 A를 조작하면 되고, C를 감소시키기 위해서는 B를 조작하면 된다.

이 문제도 위 방법을 활용하기로 했다.

먼저, 위 방법을 활용하기 위해서 숫자 배열을 Sorting했다.
이후 left는 index = 0위치에, right는 배열 끝 index에 위치시켰다.
left는 오른쪽으로밖에 이동하지 않고, right은 왼쪽으로밖에 이동하지 않는다.
이 경우, Array는 Sorting되어 있기 때문에 arr[left]는 증가만 할 것이며, arr[right]는 감소만 할 것이다.

조금 더 자세히 문제 해결을 위한 알고리즘을 구현해보자. 임의 숫자 S가 좋은 수인지 확인해보자.

1. arr[left] + arr[right] > S : arr[left] + arr[right]를 감소시켜야 한다. 따라서 right을 1 감소시킨다.

2. arr[left] + arr[right] < S : arr[left] + arr[right]를 증가시켜야 한다. 따라서 left를 1 증가시킨다.

3. arr[left] + arr[right] = S : S는 좋은 수이다

이 때 주의해야 할 점이 있다. 우리가 arr[index] = S가 좋은 수인지를 판단하고 있다 생각하자.

이 때, left = index, right = index일 때는 어떻게 될까?

문제 중에서 어떤 수가 "다른" 수 두 개의 합으로 나타낼 수 있어야 하기 때문에, 무조건 이런 경우의 수는 무시해야 한다.

따라서 위 2가지 Case에 대한 처리도 따로 해주어야 한다.

1. left = index : left를 한 칸 오른쪽 이동시킨 후 재탐색한다.

2. right = index : right를 한 칸 왼쪽 이동시킨 후 재탐색한다.

코드

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

public class Main {
	
	static int N;
	static Long[] arr;
	static long ans = 0;
	
	static void pointer(int index) {
        // 문제 풀이 설명 참조
		int left = 0;
		int right = N-1;
		while(left<right) { 
			if(left==index) {
				left++;
				continue;
			}
			if(right==index) {
				right--;
				continue;
			}
			
			long sum = arr[left]+arr[right];
			if(sum > arr[index]) {
				right--;
			}
			else if(sum==arr[index]){
				ans++;
				break;
			}
			else {
				left++;
			}
		}
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		arr= new Long[N];
		
		for(int i =0;i<N;i++) {
			arr[i] = sc.nextLong();
		}
		Arrays.sort(arr); // 현재 풀이의 핵심 부분. Sorting!
		
		for(int i =0;i<N;i++) {
            // 모든 Array 수에 대하여 좋은 수인지 판단해야 한다.
			pointer(i);
		}
		System.out.println(ans);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

결과

• 런타임 에러 : 실수로 left와 right에 고정값을 주어서 발생한 에러이다.
• 3,4,5번째 줄 틀렸습니다 : left = index, right = index인 경우를 고려하지 않아 생긴 문제이다.
• 1번째 줄 틀렸습니다 : 위 이유로 틀린 것이 맞는지 검증하기 위한 시도였다.