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

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

 

 

📌 문제

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

⚔ 제한 사항

numbers의 길이는 2 이상 100 이하입니다.

numbers의 모든 수는 0 이상 100 이하입니다.

 

---

 

👀 문제 해석

이 문제는 주어진 정수 배열 numbers 에서 서로 다른 두 개의 수를 선택해 그 합을 구한 뒤, 이를 오름차순으로 정렬하여 반환하는 문제이다.

 

각 수는 배열에서 다른 인덱스에 있는 수와 조합되어야 한다. 또한 중복된 합은 한 번만 포함해야 한다.

 

이 문제에서 중요한 점은 "서로 다른 인덱스"의 두 수를 조합해야 한다는 것과, 모든 합을 중복 없이 구한 후 오름차순으로 정렬하는 것이다.

알고리즘 분류 관점에서 보면, 이 문제는 조합(combination)이라고 할 수 있다. 단순하게 볼 때 모든 경우의 수를 구하면 쉽게 풀릴 수 있다. 또한, 중복을 방지하고 결과를 정렬하는 과정이 포함되므로 정렬(sort)과 집합(set) 자료구조의 개념을 활용할 수 있다. 기본적으로 탐색과 정렬 알고리즘을 사용하여 해결할 수 있는 문제이다. 

 

 

🔎 접근

이 문제를 풀기 위해서는 주어진 배열 numbers에서 두 개의 수를 선택한 후 그 합을 계산하고, 이를 중복 없이 저장한 뒤 오름차순으로 정렬하는 과정이 필요하다.

 

우선 배열의 길이가 2 이상 100 이하로 제한되어 있어, 모든 경우의 수를 탐색하는 것으로 풀 수 있다. 배열의 최대 길이가 100이므로, 최악의 경우에는 100개의 수 중 두 개를 선택하는 조합(100C2)을 구해 총 4950번의 연산이 발생할 수 있다. 이는 충분히 효율적인 범위 내에 있는 계산량이므로, 브루트 포스 방식(모든 가능한 경우의 수를 탐색하는 방식)으로 문제를 해결할 수 있다.

 

첫 번째로 고려할 방법은 이중 반복문을 사용해 배열 내에서 모든 두 수의 조합을 계산하는 것이다. 여기서 중요한 것은 두 가지이다. 첫째, 같은 인덱스에 있는 수를 중복 선택하지 않아야 하고, 둘째, 같은 합이 여러 번 나오는 경우 중복을 제거해야 한다는 것이다. 이를 위해 set 을 사용하면 편리할 듯 하다. 

 

또한, 문제의 제한 사항 중에서 배열의 각 요소가 0 이상 100 이하의 정수라는 조건이 있는데, 이는 합계의 범위가 0부터 200까지임을 의미한다. 따라서, 이러한 값 범위 내에서 결과를 처리하는 것이 가능하다.

💡 풀이 과정 

import java.util.*;
import java.util.stream.IntStream;

class Solution {
    public int[] solution(int[] numbers) {
        Set<Integer> results = new HashSet<>();

        // 두 수의 합을 Set에 추가
        IntStream.range(0, numbers.length)
                 .forEach(i -> IntStream.range(i + 1, numbers.length)
                                        .forEach(j -> results.add(numbers[i] + numbers[j])));

		Arrays.sort(results.toArray())

        return results.stream()
                      .mapToInt(Integer::intValue)
                      .toArray();
    }
}

 

 

위 코드는 numbers 배열에서 두 개의 서로 다른 인덱스에 있는 수들의 합을 구한 후, 이를 중복 없이 저장하고 오름차순으로 정렬하여 배열로 반환하는 방식이다.

 

여기서 for문 대신 IntStream을 사용하여 간결하게 모든 조합을 처리하도록 했다. 또한 결과를 리턴하기 위해 Set 자료구조를 사용해 각 조합의 합을 중복을 자동으로 제거한다.

 

그런데 이 방식으로 제풀했을 때 문제가 있다! 

 

다음과 같이 일부 테스트 케이스에 대해서는 성공하나, 일부에 대해서는 실패한다. 

 

 

 

반례가 무엇일까?

 

실패하는 반례는 다음과 같다.

 

입력값: [8, 1, 7, 10, 70]
기댓값: [8, 9, 11, 15, 17, 18, 71, 77, 78, 80]

 

첫 번째 코드는 이 테스트 케이스에서 실패하는데, 그 이유는 무엇일까?

 

 

 

문제의 원인

첫 번째 코드에서 사용한 Arrays.sort(results.toArray())가 문제의 원인이다.

 

results.toArray()는 Object[] 타입의 배열을 반환하며, Arrays.sort()가 배열을 정렬해도 Set 자체는 변하지 않는다. 즉, 정렬된 배열은 임시 배열일 뿐, 결과값에 반영되지 않는다.

 

또한, HashSet은 본래 순서를 보장하지 않는 자료구조이다. 따라서 HashSet에 저장된 값이 삽입 순서와 무관하게 저장되기 때문에, 결과적으로 배열을 정렬하지 않으면 결과값이 의도한 대로 오름차순으로 출력되지 않을 수 있다.

 

정말 신기하게도 Arrays.sort 를 빼도 예시에서 정답으로 제시된 결과가 나온다. 

 

 

 

프로그래머스에서 의도적으로 이런 테스트 케이스를 예시로 제시한 게 아닐까 하는 합리적 의심을 해볼 수 있을 것 같다. 

 

두 번째 코드 

 

다음과 같은 코드로 변경해보았다. 

 

import java.util.*;
import java.util.stream.IntStream;

class Solution {
 	public int[] solution(int[] numbers) {

		Set<Integer> results = new HashSet<>();

		IntStream.range(0, numbers.length).forEach(i ->
			IntStream.range(i + 1, numbers.length).forEach(j ->
				results.add(numbers[i] + numbers[j])
			)
		);

		return results.stream().sorted().mapToInt(Integer::intValue).toArray();
	}
}

 

 

 

results.stream().sorted()를 통해 스트림에서 정렬을 명시적으로 수행하여 항상 올바르게 정렬된 배열을 반환한다. 이를 통해 다양한 테스트 케이스에서 일관된 결과를 얻을 수 있다.

 

왜 그럴까? 첫 번째 코드와 두 번째 코드의 차이점은 Arrays.sort()와 stream().sorted()를 사용하는 방식에서 비롯된다.

 

Stream의 sorted()는 results의 데이터를 오름차순으로 정렬된 스트림으로 변환한다. Set의 순서가 보장되지 않더라도, 스트림에서 정렬을 명시적으로 수행하기 때문에 항상 정렬된 결과를 얻을 수 있다. 이후 정렬된 스트림을 int[]로 변환해 최종 결과를 반환하는 방식이다.

 

 

 

🚀 최종 제출 코드 

 

import java.util.*;
import java.util.stream.IntStream;

class Solution {
    public int[] solution(int[] numbers) {
        Set<Integer> results = new HashSet<>();

        // 두 수의 합을 Set에 추가
        IntStream.range(0, numbers.length).forEach(i ->
            IntStream.range(i + 1, numbers.length).forEach(j ->
                results.add(numbers[i] + numbers[j])
            )
        );

        // Stream에서 직접 정렬 후 배열로 변환하여 반환
        return results.stream().sorted().mapToInt(Integer::intValue).toArray();
    }
}

 

 

 

☘️ 이 문제에서 사용한 정렬 알고리즘 

 

이 문제에서 사용한 정렬 알고리즘에 대해 좀 더 알아보자. 

 

Arrays.sort()와 stream().sorted() 모두 자바에서 정렬을 수행하지만, 사용하는 알고리즘이 다르며 적용되는 자료형에 따라 성능에 차이가 발생한다.

Arrays.sort()와 stream().sorted()`의 차이점

1. Arrays.sort():
   - Primitive 타입 배열 (int[], double[] 등)을 정렬할 때는 듀얼 피봇 퀵소트(Dual-Pivot Quicksort) 알고리즘을 사용한다.
   - Wrapper 타입 (Integer[], Double[] 등)이나 객체 배열을 정렬할 때는 팀소트(Timsort) 알고리즘을 사용한다.
   - 듀얼 피봇 퀵소트는 퀵소트의 변형으로, 두 개의 피봇을 사용하여 배열을 세 부분으로 분할해 정렬한다. 평균적으로 빠른 성능을 제공하지만, 최악의 경우 O(n²)의 시간 복잡도를 가질 수 있다.
   - 팀소트는 합병 정렬과 삽입 정렬을 결합한 하이브리드 알고리즘으로, 최악의 경우에도 O(n log n)의 시간 복잡도를 보장한다. 특히 거의 정렬된 배열에서 성능이 뛰어나다.
  
2. stream().sorted():
   - stream().sorted()는 객체 기반의 정렬에 사용되며, 내부적으로 팀소트(Timsort) 알고리즘을 사용한다.
   - 이 방식은 컬렉션이나 객체 배열의 스트림에서만 사용되며, 정렬 후 결과를 다시 int[] 같은 기본 배열로 변환할 수 있다.
   - 스트림은 함수형 프로그래밍 스타일을 지원하며, 중간 연산에서 정렬을 처리하고, 최종적으로 결과를 반환하는 방식이다. 이 과정에서 lazy evaluation으로 성능 최적화가 가능하다.

 

정렬 알고리즘 비교

 

듀얼 피봇 퀵소트 (Dual-Pivot Quicksort)
- 알고리즘: 퀵소트의 변형으로, 두 개의 피봇을 사용해 배열을 세 부분으로 나누어 정렬한다.
- 적용 대상: 주로 primitive 타입 배열에 사용된다.
- 시간 복잡도: 평균적으로 O(n log n)이지만, 최악의 경우 O(n²)까지 성능이 저하될 수 있다.
- 공간 복잡도: O(log n).

팀소트 (Timsort)
- 알고리즘: 합병 정렬과 삽입 정렬을 결합한 하이브리드 알고리즘으로, 정렬된 데이터에 대해 최적화된 성능을 보인다.
- 적용 대상: 주로 객체 배열이나 컬렉션 정렬에 사용되며, stream().sorted()에서 활용된다.
- 시간 복잡도: 평균 및 최악의 경우 O(n log n)이며, 거의 정렬된 배열에서는 O(n)의 성능을 발휘한다.
- 공간 복잡도: O(n).

 

요약

- Arrays.sort()는 primitive 타입 배열에서 듀얼 피봇 퀵소트를 사용하며, Wrapper 타입이나 객체 배열에서는 팀소트를 사용한다.
- stream().sorted()는 객체 기반 스트림 정렬에 사용되며, 내부적으로 팀소트를 활용한다.
- 두 알고리즘 모두 효율적인 정렬을 제공하지만, 팀소트는 최악의 경우에도 O(n log n) 성능을 보장하는 반면, 듀얼 피봇 퀵소트는 최악의 경우 O(n²)로 성능이 저하될 수 있다.
- Primitive 배열을 정렬할 때는 Arrays.sort()가, 객체 배열이나 스트림을 다룰 때는 stream().sorted()를 사용하는 것이 더 적합하다.