[백준] 3273. 두 수의 합 (JAVA)

이번에 풀어 볼 문제는 <백준 3273번.  두 수의 합>이다.

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

📌 문제 탐색하기

목표

합이 x 가 되는 두 숫자의 쌍 개수 구하기

해야 할 것

1. 모든 쌍을 다 구해봐도 시간은 충분할까?

2. 합이 x 가 되는 개수를 어떻게 셀까?

입력

[첫줄] n : 수열의 크기 ( 1 ≤ n ≤ 100000 )

[둘째줄] 수열

[셋째줄] x ( 1 ≤ x ≤ 2000000 )

아이디어

1. 모든 쌍을 다 구해봐도 시간은 충분할까? 

➡️ n의 최대값이 10^5 이므로 모든쌍을 다구하면 경우의 수가 10^5 *(10^5-1) 이 되어 시간초과가 날 가능성이 있어 보인다. O(nlogn) 이하의 시간복잡도를 갖는 알고리즘이 필요하다.

 

2. 먼저 정렬을 하고 두 수를 뽑으면, 두 수의 합이 일정 범위를 넘어가면 멈출 수 있어 연산량을 줄일 수 있겠다.

➡️정렬에 필요한 시간복잡도 O(nlogn) 

 

3.투 포인터 아이디어를 사용해서 start는 배열의 첫번째 지점, end는 배열의 마지막 지점에 위치시킨다.

만약 arr[start] + arr[end] 가 x보다 작으면 start를 오른쪽으로 한 칸 이동시키고,

arr[start] + arr[end] 가 x보다 크거나 같다면 end를 왼쪽으로 한 칸 이동시킨다.

start 와 end 의 위치가 같아지면 탐색을 중단시킨다.

➡️O(n) 의 시간복잡도로 탐색이 가능하다

 

📌 코드 설계하기

1. input 순열을 받고, 배열로 저장한다.

2. 배열을 오름차순으로 정렬해둔다.

3.  int start, int end 변수를 선언하고 start는 배열의 첫 번째 지점, end는 배열의 마지막 지점에 위치시킨다. 

4. 숫자 쌍의 개수를 셀 int count = 0 으로 초기화해둔다.

5. arr[start] + arr[end]가 x보다 작으면 start++; ,

arr[start] + arr[end] 가 x보다 크면 end--;

arr[start] + arr[end] == x 이면 count++ 를하고 end --; 

6. start == end가 되면 탐색을 종료한다.

7. 최종 count를 출력한다.

📌 정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

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());

        // 배열 정렬 O(nlogn)
        Arrays.sort(arr);

        // 두 포인터 초기화
        int start = 0;
        int end = n - 1;
        int count = 0;

        // 탐색 시작
        while (start < end) {
            int sum = arr[start] + arr[end];
            if (sum < x) {
                start++;
            } else if (sum > x) {
                end--;
            } else {
                count++;
                start++;
                end--;
            }
        }

        System.out.println(count);
    }
}

📌 알게 된 것

JAVA의 Arrays.sort()는 Dual-Pivot Quicksort 알고리즘을 사용한다고 한다. 이 알고리즘의 시간복잡도는 다음과 같다.

• 평균 시간복잡도: O(nlog⁡n)
• 최악의 경우 시간복잡도: O(n^2)

그러나 Java의 Arrays.sort()는 최악의 경우 O(n^2) 복잡도를 갖는 전통적인 퀵소트와 달리 최적화된 Dual-Pivot Quicksort를 사용하여 이론적인 최악의 경우를 피할 수 있도록 설계되었다고 한다.

이를 통해 대부분의 실제 사용 사례에서는 O(nlogn) 성능을 유지한다고 한다.

또한, Java 7 이상에서는 Arrays.sort()가 작은 배열에 대해 삽입 정렬로 전환하여 더 효율적으로 동작한다고 하니, 기본적으로 Arrays.sort()는 O(nlogn)의 시간 복잡도를 가진다고  생각하고 사용하면 되겠다.