🔍 Problem

두 수의 합

---

📃 Input&Output

---

🌁 문제 배경

가. 문제 설명
특정조건안에서 수열 속 두 수의 합이 원하는 숫자인 경우의 수를 찾는 문제이다.

나. 접근 방법
수열을 정렬하고 투포인터를 사용할 것이다.

다. 사용할 알고리즘 선택
투포인터

---

📒 수도 코드

가. 수열을 먼저 정렬한다.
정렬되어 있어야만 조건보다 크면 오른쪽 포인터를 줄이고, 작으면 왼쪽 포인터를 늘리는 식의 판단이 가능하기 때문에 탐색하고자하는 수열을 먼저 정렬합니다.

Arrays.sort(arr);

나. start와 end를 수열의 시작과 끝의 인덱스로 지정하고 투포인트 사용
투포인터의 핵심이 양쪽에서 좁히는 것이기 때문에, 양쪽 끝에서부터 시작합니다.

start = 0;
end = arr.length - 1;

다. 투포인트 실행

while (start < end) {
            int sum = arr[start] + arr[end];
            if (sum < num) {
                start++;
            } else if (sum > num) {
                end--;
            } else {
                cnt++;
                start++;
            }
        }

해당 투포인터의 조건은 다음과 같습니다.

1. $sum > N : start ++$
2. $sum <N : end--$
3. $sum==N : count++, start ++$

이유는 아래와 같습니다.

$Sum$이 $N$보다 작다는 것은 $end$를 줄여 $Sum$을 줄여야 한다는 것을 의미하고
$Sum$이 $N$보다 크다는 것 $start$를 늘려 $Sum$을 키워야 한다는 것을 의미한다.
그리고 두개가 같다면, $start$를 늘려 다음 가능한 쌍을 확인하고 $count$, 즉 경우의 수를 하나 늘리는 것이다.

그렇다면 여기서 의문이 하나 생길 수 있다. 왜 start를 +1하는가? end를 -1하면 안되나?
이것에 대한 해답은 다음과 같다.

둘다 해도 된다.

별로 차이 나지 않는 것을 확인.

---

💻 Code

import java.util.*;

public class P3273 {

    static int N;
    static int[] arr;
    static int num;
    static int cnt = 0;
    static int start, end;

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();

        arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);

        num = sc.nextInt();

        start = 0;
        end = arr.length - 1;

        while (start < end) {
            int sum = arr[start] + arr[end];
            if (sum < num) {
                start++;
            } else if (sum > num) {
                end--;
            } else {
                cnt++;
                start++;
            }
        }

        System.out.println(cnt);
    }

}

---

🤔 느낀점

정렬된 배열에서 써야한다는 점이 인상적이였다.