문제 이해

숫자 배열이 주어진다.
이 중 2가지 숫자를 선택하여 두 수의 합이 x가 되는 쌍의 개수를 구하는 문제이다.

문제 풀이

a + b = K일 때를 생각해보자.
b가 감소하면 K값 또한 감소할 것이고, a가 증가하면 K값 또한 증가할 것이다.
그래서 이 문제에서 두 수의 합을 만드는 쌍 개념을 아래와 같이 잡았다.

(a,b) = (증가만 할 수 있는 수, 감소만 할 수 있는 수)

위와 같은 방법을 사용하기 위해 먼저 숫자 배열을 정렬시켰다.
그렇다면 배열의 시작점에는 배열의 최솟값이, 배열의 마지막 공간에는 배열의 최댓값이 위치해 있을 것이다.
이후 2개의 포인터를 활용하겠다.

먼저 1개 포인터는 a를 나타내는 포인터로써 특정 조건 때 오른쪽으로 포인터가 이동하여 이전에 선택했던 a보다 큰 값을 선택한다.
남은 1개 포인터는 b를 나타내는 포인터로써 특정 조건 때 왼쪽으로 포인터가 이동하여 이전에 선택했던 b보다 작은 값을 선택한다.

포인터 이동 조건은 아래와 같다.

1. a + b > x일 때 : a + b는 작아져야 한다. 따라서 b가 작아져야 하므로 b를 가리키는 포인터가 왼쪽으로 이동한다.

2. a + b < x일 때 : a + b는 커져야 한다. 따라서 a가 커져야하고, a를 가리키는 포인터가 오른쪽으로 이동한다.

3. a + b = x일 때 : 1개의 쌍이 선택되었다. 숫자 배열은 "서로 다른 양의 정수"라는 조건이 있기 때문에 덧셈의 특성 상 (a,b) 이외의 방법으로 a나 b를 활용하여 x를 만드는 경우의 수는 존재하지 않는다. 따라서 a 포인터는 오른쪽으로, b 포인터는 왼쪽으로 모두 이동시킨다.

• 덧셈의 특성 : a + b = x일 때, a = x - b라고 생각할 수 있다. x - b의 값이 2개일 수는 없으므로, a는 항상 하나로 결정되어 있으며, 중복되지 않는 한 (a,b) 이외의 방법으로 a나 b를 활용하여 x를 만들 수는 없다.

코드

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

public class Main {
	
	static int n, x;
	static Integer[] arr;
	
	static void find() {
        // 두 포인터를 활용한 알고리즘
		int left = 0;
		int right = n-1;
		int ans = 0;
		int sum;
		while(left<right) {
			sum = arr[left]+arr[right];
			
			if(sum > x) {
                // 문제 풀이 1번 상황
				right--;
			}
			else if(sum==x) {
                // 문제 풀이 3번 상황
				left++;
                right--;
				ans++;
			}
			else {
                // 문제 풀이 2번 상황
				left++;
			}
		}
		System.out.println(ans);
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		n = sc.nextInt();
		arr = new Integer[n];
		for(int i =0;i<n;i++) {
			arr[i] = sc.nextInt();
		}
		Arrays.sort(arr); // 이번 풀이에서 가장 핵심인 부분! Sorting
		x = sc.nextInt();
		
		find();
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

결과