[백준] 두 수의 합

두 수의 합 문제 해결

주어진 수열에서 두 수를 뽑아 그 합이 특정 값 x가 되는 쌍의 개수를 찾는 문제입니다. 수열의 크기 n, 수열의 각 요소, 그리고 목표 합 x가 주어집니다. 이때, 조건을 만족하는 (ai, aj) 쌍의 수를 출력해야 합니다.

문제 조건

• 시간 제한: 1초
• 메모리 제한: 128MB
• 제출: 54829
• 정답: 19665
• 맞힌 사람: 14545
• 정답 비율: 34.681%
• 문제 링크

3273번: 두 수의 합

입력

첫째 줄에 수열의 크기 n이 주어집니다. 둘째 줄에 수열의 요소가 공백으로 구분되어 주어집니다. 셋째 줄에 자연수 x가 주어집니다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

조건을 만족하는 (ai, aj) 쌍의 개수를 출력합니다. (ai + aj = x, 1 ≤ i < j ≤ n)

주요 개념

주어진 수열의 요소와 X 값에 따라, 가능한 모든 쌍의 조합 중 조건을 만족하는 쌍의 개수를 계산합니다.
각 숫자가 수열에 몇 번 등장하는지 카운팅하기 위한 배열(cnt)을 사용합니다.
이 배열은 수열에 포함된 각 숫자를 인덱스로 하고, 해당 인덱스에 해당하는 숫자의 등장 횟수를 값으로 합니다.
X의 절반 값까지만 반복하여 각 숫자에 대해 X - i 값이 존재하는지 확인하고,
존재한다면 해당 숫자의 등장 횟수와 X - i의 등장 횟수를 곱한 값을 결과에 더합니다. 이 방식으로 중복 계산을 방지합니다.

코드 설명

import java.util.Scanner;

public class SumOfTwoNumbers {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in); // 입력을 받기 위한 Scanner 객체 생성
        int N = sc.nextInt(); // 수열의 크기 N 입력 받기
        int[] a = new int[N]; // 수열을 저장할 배열 선언
        for (int i = 0; i < N; i++) // N번 반복하여 수열의 요소 입력 받기
            a[i] = sc.nextInt();
        int X = sc.nextInt(); // 목표 합 X 입력 받기

        int[] cnt = new int[1000001]; // 각 숫자의 등장 횟수를 저장할 배열 선언
        for (int i = 0; i < N; i++) // 수열의 각 요소에 대해 등장 횟수 카운팅
            cnt[a[i]]++;

        long ans = 0; // 조건을 만족하는 쌍의 수를 저장할 변수 선언
        for (int i = 1; i <= (X - 1) / 2; i++) // 1부터 X의 절반까지 반복
            if (X - i <= 1000000) // X-i가 배열 범위 내에 있는지 확인
                ans += (long)cnt[i] * cnt[X - i]; // 조건을 만족하는 쌍의 개수 계산하여 ans에 더하기
        System.out.println(ans); // 계산된 쌍의 개수 출력
    }
}