[백준/Java] 3273: 두 수의 합

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

 

---

 

문제

n개의 서로 다른 양의 정수(a1, a2, ..., an)로 이루어진 수열 존재

자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구해야 함

 

제한사항

• 1 ≤ ai ≤ 1,000,000
• 1 ≤ 정수 개수 n ≤ 100,000
• 1 ≤ 자연수 x ≤ 2,000,000

 

---

풀이1 (정렬 + 투 포인터)

1. 수열 오름차순 정렬

값의 크기 비교를 통해 포인터 이동 방향을 결정해야 하기 때문

 

2. 투 포인터 사용

• p1: 배열의 시작 (가장 작은 값)
• p2: 배열의 끝 (가장 큰 값)

 

3. 반복하면서 합 비교

sum = arr[p1] + arr[p2]

• sum이 x보다 작은 경우
  • 값이 작으므로 더 큰 값 필요
  • p1++
• sum이 x보다 큰 경우
  • 값이 크므로 더 작은 값 필요
  • p2--
• sum이 x와 같은 경우
  • p1++, p2-- (이미 사용한 값이므로 둘 다 이동)

 

🎯 투 포인터는 합의 크기에 따라 이동 방향이 달라야 함

 

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public 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[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int x = Integer.parseInt(br.readLine());

        Arrays.sort(arr);   // 입력 받은 배열 정렬

        // 포인터 위치 지정
        int p1 = 0;
        int p2 = n - 1;

        int ans = 0;    // 쌍의 개수

        while (p1 < p2) {
            if (arr[p1] + arr[p2] > x) {    // 합이 x보다 작은 경우 p1 증가
                p2--;
            } else if  (arr[p1] + arr[p2] < x) {    // 합이 x보다 큰 경우 p2 감소
                p1++;
            } else {
                ans++;
                p1++;
                p2--;
            }
        }

        System.out.println(ans);
    }

}

 

---

 

풀이2 (boolean 배열 사용)

현재 숫자 ai를 봤을 때, x - ai 값이 존재하는지 확인

--> boolean 배열로 확인 가능

 

1. visited 배열 생성

수열의 숫자가 이미 등장했는지 체크하는 배열

ai의 최대값이 1,000,000이므로 boolean[1000001] 배열 생성

 

2. 수열을 하나씩 순회하며 visited[x - ai] 값이 존재하면 쌍 발견

현재 숫자와 대응되는 수가 수열에 존재한다는 뜻이므로, 쌍의 개수 +1

 

3. 존재하지 않는 경우 현재 값을 visited에 저장

 

🎯 값의 범위가 제한되어 있고 작으므로 boolean 배열을 사용하는 것이 빠름
이미 수열이 정렬 되어있는 경우엔 투 포인터를 사용해도 무관

 

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public 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[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int x = Integer.parseInt(br.readLine());
        //////////////////
        boolean[] visited = new boolean[1000001];   // 숫자 존재 여부 저장. ai 최대값
        int ans = 0;

        for (int ai : arr) {
            int target = x - ai;

            // target이 범위 안이고 이미 등장했다면
            if (target > 0 && target <= 1000000 && visited[target]) {
                ans++;
            }

            visited[ai] = true;
        }

        System.out.println(ans);
    }

}