[프로그래머스/JAVA] 두 개 뽑아서 더하기

https://school.programmers.co.kr/learn/courses/30/lessons/68644

프로그래머스

 

📌 문제 요약 

정수 배열 numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더한 뒤, 모든 가능한 결과를 배열에 오름차순으로 반환하는 문제입니다.
조건:

1. 동일한 합은 중복을 제거합니다.
2. 결과는 반드시 오름차순이어야 합니다.

---

[ 오답 노트 ]

❌ 기존 오답 코드

결과값은 맞게 나오지만 시간 초과가 나서 오답처리 되었다. ㅠㅜ

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        ArrayList<Integer> answer = new ArrayList<>();
        Arrays.sort(numbers); // [1,1,2,3,4]
        
        int sum = 0;
        for(int i = 0; i < numbers.length; i++) {
            for(int j = i+1; j < numbers.length; j++) {
                sum = (numbers[i] + numbers[j]); // 2
                if(!answer.contains(sum)){
                    answer.add(sum);
                }
            }
        }
        
        return answer.stream().mapToInt(i->i).toArray();
    }
}

📌 기존 코드의 문제점

1. answer.contains()의 비효율성:
   • contains() 메서드는 리스트를 순차적으로 탐색하여 중복 여부를 확인합니다. 리스트의 크기가 커질수록 탐색 시간이 선형적으로 증가합니다.
   • 이 연산이 이중 루프 안에서 실행되기 때문에, 전체 시간 복잡도가 O(n4)O(n^4)O(n4)로 매우 비효율적입니다.
2. 비효율적인 정렬:
   • Arrays.sort(numbers)는 불필요한 연산입니다. 더한 값을 처리할 때 배열의 정렬 상태가 중요하지 않으므로, 성능에 도움이 되지 않습니다.
3. 시간 초과 가능성:
   • 문제에서 제공된 numbers 배열의 최대 크기인 100100100이 적용될 경우, O(n4)O(n^4)O(n4)는 매우 느려져 시간 초과가 발생할 가능성이 큽니다.

---

[ 정답 코드 & 올바른 풀이 ]

📌 올바른 풀이

1. HashSet 사용:
   • HashSet은 중복된 값을 자동으로 제거합니다. 따라서, 리스트를 사용해 중복 여부를 확인할 필요가 없습니다.
   • HashSet.add()의 시간 복잡도는 평균적으로 O(1)입니다.
2. 정렬:
   • HashSet은 순서를 보장하지 않으므로, 결과를 배열로 변환할 때 정렬이 필요합니다.
   • stream().sorted()를 사용하여 시간 복잡도 O(klog⁡k)로 정렬합니다.
3. 시간 복잡도 개선:
   • 이중 루프는 여전히 O(n^2)이지만, 중복 확인이 O(1)로 처리되므로 전체 시간 복잡도는 O(n^2)로 대폭 감소합니다.

 

📌 시간 복잡도 비교 

코드	시간복잡도	비교
원래 코드	O(n^4)	contains 호출의 비효율성으로 인해 시간 초과
개선된 정답 코드	O(n^2)	HashSet으로 중복 제거를 효율화

---

📌 정답 코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        // HashSet 사용해 중복된 값 제거
        Set<Integer> answer = new HashSet<>();

        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                answer.add(numbers[i] + numbers[j]);
            }
        }

        // 중복된 제거된 합들을 정렬된 배열로 변환
        return answer.stream().sorted().mapToInt(i -> i).toArray();
    }
}