[Baekjoon] 3273번: 두 수의 합

https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

문제 설명

n개의 서로 다른 양의 정수로 이루어진 수열이 있다. 정수는 모두 1보다 크거나 같고 1_000_000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때 합이 x가 되는 두 수로 이루어진 쌍의 수를 구하는 프로그램을 작성해라.

풀이 방법 - 정렬, 투 포인터

기본적인 투 포인터 문제이다. 이 문제는 정렬과 투 포인터를 활용하면 쉽게 해결할 수 있다.

정렬하면 제일 왼쪽이 최솟값이고 제일 오른쪽이 최댓값이 된다. 따라서 두 값을 더해서 x와 비교하면서 포인터를 움직이면 된다. 그리 어렵지 않으니 바로 코드로 이해하자.

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

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[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int target = Integer.parseInt(br.readLine());

        Arrays.sort(nums);

        int left = 0;
        int right = n - 1;
        int ans = 0;

        while (left < right) {
            int sum = nums[left] + nums[right];

            // 서로 다른 수들로 이루어진 수열이므로 중복은 신경쓸 필요 없다.
            if (sum == target) {
                ans++;
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        System.out.print(ans);
    }
}