[BOJ 3272번/HashMap] 두 수의 합 (Java)

문제 링크

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

3273번: 두 수의 합

백준 3273번 문제는 수열과 합 문제로, 길이가 n인 수열과 정수 x가 주어졌을 때, 수열에서 두 원소를 선택하여 그 합이 x가 되는 경우의 수를 구하는 문제이다.

 

풀이방법

1) 투 포인터(Two Pointers)를 이용한 방법

 - 투 포인터 알고리즘을 통한 문제해결 동작 방식

• 시작점(start)과 끝점(end)을 첫 번째 원소의 인덱스(0)로 초기화합니다. 
• start와 end의 원소를 더한 값이 x보다 작으면, end를 1 증가시킵니다. 
• start와 end의 원소를 더한 값이 x보다 크면, start를 1 증가시킵니다. 
• start와 end의 원소를 더한 값이 x와 같으면, 경우의 수를 1 증가시키고, start와 end를 각각 1 증가시킵니다. 
• start가 end보다 커지면 알고리즘을 종료합니다.

 - 투 포인터 알고리즘을 통해 문제를 해결하기 위한 Java 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        int x = sc.nextInt();

        int ans = 0;
        int start = 0;
        int end = n-1;
        Arrays.sort(a); // 수열을 정렬합니다.

        while (start < end) {
            int sum = a[start] + a[end];
            if (sum == x) { // 합이 x와 같으면 경우의 수를 1 증가시키고, start와 end를 각각 1 증가시킵니다.
                ans += 1;
                start += 1;
                end -= 1;
            } else if (sum < x) { // 합이 x보다 작으면, end를 1 증가시킵니다.
                start += 1;
            } else { // 합이 x보다 크면, start를 1 증가시킵니다.
                end -= 1;
            }
        }

        System.out.println(ans);
        sc.close();
    }
}

 - 시간복잡도

수열을 정렬하는 부분에서 O(n log n)의 시간 복잡도를 갖고 나머지 부분에서는 O(n)의 시간 복잡도를 가지므로, 전체적인 시간 복잡도는 O(n log n)이다.

 

 

 

2) HashMap을 이용한 방법

 - HashMap의 개념

• Key-Value 쌍으로 이루어진 데이터를 저장하고 검색하는 데에 최적화된 자료구조이다.
• 내부적으로 배열과 LinkedList를 사용하여 데이터를 저장하고, 해시 함수를 이용하여 Key의 해시값을 계산한다.
• 이를 통해 검색 속도를 O(1)로 유지할 수 있다.

 

 - HashMap의 특징

• Key-Value 쌍으로 이루어진 데이터를 저장할 수 있다.
• Key는 중복될 수 없지만, Value는 중복될 수 있다. 
• 데이터를 저장할 때는 Key를 기반으로 해시값을 계산하여 저장한다. 
• Key의 순서는 보장되지 않는다.

 -  HashMap을 통한 문제해결 동작 방식

• 숫자들의 등장 횟수를 해시맵에 저장합니다. 
• 각 숫자 x에 대해서, 만약 target-x가 해시맵에 있다면, x와 target-x가 한 쌍이므로 쌍의 개수를 증가시킵니다. 
• 쌍의 개수를 출력합니다.

 - HashMap을 통해 문제를 해결하기 위한 Java 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        Map<Integer, Integer> map = new HashMap<>();

        // 해시맵에 각 숫자의 등장 횟수 저장
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            if (!map.containsKey(a[i])) {
                map.put(a[i], 1);
            } else {
                map.put(a[i], map.get(a[i]) + 1);
            }
        }

        int target = sc.nextInt();
        int cnt = 0;

        // 각 숫자 x에 대해서 target-x가 해시맵에 있는지 검사
        for (int x : a) {
            if (map.containsKey(target - x)) {
                cnt += map.get(target - x);
            }
            // 자기 자신과의 쌍은 하나로 셈
            if (target - x == x) {
                cnt--;
            }
        }

        System.out.println(cnt / 2);
        sc.close();
    }
}

 - 시간복잡도

해시맵에 각 숫자의 등장 횟수를 저장하는 데에 O(n)의 시간이 소요됩니다. 그리고 각 숫자에 대해 해시맵을 검색하므로, 검색에 O(1)의 시간이 소요됩니다. 전체 시간 복잡도는 O(n)입니다.

 

 

두 풀이 방법의 비교

1) 시간복잡도 비교

 - HashMap의 시간복잡도 : O(n)
 - 투 포인터 방법의 시간복잡도: O(n log n)

 

1) 공간복잡도 비교

 - HashMap은 입력받은 배열을 이용해 다시 HashMap을 구성해야 하기 때문에 메모리를 많이 사용하게 된다. 따라서, 입력의 범위가 매우 크다면 메모리 초과가 발생할 수 있고, 이러한 경우에는 투 포인터(Two Pointers) 알고리즘 등을 이용하여 메모리를 덜 사용하는 방법을 고민해볼 수 있습니다.