CT | 백준 3273번 두 수의 합

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

 

배열의 기본 문제를 간단하게 풀어봤습니다. 

처음에 제가 생각한 풀이 방식은

import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(scanner.nextInt());
        }

        int num = scanner.nextInt();
        scanner.close();
        int cnt = 0;
        for (int i = 0; i < list.size(); i++) {
            for (int j = 1; j < list.size(); j++) {
                if (num == list.get(i) + list.get(j)) {
                    cnt++;
                }
            }
        }
        System.out.println(cnt / 2);
    }
}

해당 코드였지만, 

시간초과가 발생하여 Set을 사용해 문제를 다시 풀어봤습니다. 

 

import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set.add(scanner.nextInt());
        }

        int num = scanner.nextInt();
        scanner.close();
        int cnt = 0;

        for (Integer value : set) {
            int complement = num - value;
            if (set.contains(complement)) {
                cnt++;
            }
        }

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

주요 차이점

1. 자료 구조:
   • 원본 코드: ArrayList<Integer> list를 사용하여 모든 숫자를 저장합니다. 이 리스트는 중복된 값을 허용합니다.
   • 수정된 코드: Set<Integer> set을 사용하여 숫자를 저장합니다. HashSet은 중복 값을 허용하지 않으며, 이를 통해 불필요한 중복 계산을 방지합니다.
2. 중첩 루프:
   • 원본 코드: 두 개의 중첩된 for 루프를 사용하여 리스트의 모든 쌍 (i, j)를 비교합니다. 이 방식은 O(n^2)의 시간 복잡도를 가집니다.
   • 수정된 코드: 하나의 for 루프와 Set.contains 메서드를 사용하여 보완값을 확인합니다. 이로 인해 전체 알고리즘의 시간 복잡도가 O(n)으로 줄어듭니다.
3. 계산 로직:
   • 원본 코드: 두 개의 인덱스를 사용하여 모든 쌍의 합을 계산하고, 특정 합(num)과 일치하는지를 비교합니다.
   • 수정된 코드: 각 요소의 보완값(num - value)이 존재하는지를 확인하는 방식으로, 각 쌍의 합을 직접적으로 계산하지 않습니다.
4. 출력:
   • 두 코드 모두 결과를 2로 나누어 출력합니다. 이는 각 쌍 (a, b)와 (b, a)가 두 번 계산되기 때문에 중복을 피하기 위함입니다.

요약

• 성능: 수정된 코드는 더 효율적이며, 입력 데이터의 크기가 클 경우에도 시간 초과 문제를 피할 수 있습니다.
• 구조적 차이: 리스트 대신 집합을 사용하여 중복을 방지하고, 이중 루프를 제거하여 간단한 로직으로 변경했습니다.