[프로그래머스] 두개 뽑아서 더하기 (자바 & 코틀린 풀이)
📌 문제
정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.
⚔ 제한 사항
- numbers의 길이는 2 이상 100 이하입니다.
- numbers의 모든 수는 0 이상 100 이하입니다.
입력 & 출력
| numbers | result |
| [2,1,3,4,1] | [2,3,4,5,6,7] |
| [5,0,2,7] | [2,5,7,9,12] |
👀 문제 해석
이 문제는 주어진 정수 배열 numbers에서 서로 다른 두 수를 골라 더한 값으로 만들 수 있는 모든 조합을 구한 뒤, 이들을 중복 없이 정렬하여 반환하는 문제이다. 구체적으로는 배열 내에서 인덱스가 서로 다르면서도 값은 같을 수 있는 두 수를 골라 합산한 뒤, 모든 가능한 합산 결과를 오름차순으로 정렬하여 중복을 제거한 형태로 반환하라는 의미이다.
알고리즘적으로 보면 이 문제는 두 가지 관점에서 접근할 수 있다. 먼저, 입력 크기가 2 ≤ n ≤ 100으로 제한되어 있어 복잡도에 대한 부담이 없다. 실제로 최악의 경우에도 가능한 조합 개수는 C(100, 2) = 4,950개에 불과하므로, 시간 복잡도 O(n²) 수준이면 충분히 통과된다. 따라서 아래와 같이 이중 for 문을 활용한 완전 탐색(Brute Force) 방식으로도 성능상 문제가 없다.
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();
}
}
하지만 이번 풀이에서는 깊이 우선 탐색(DFS)을 통해 모든 숫자 조합을 탐색하여 결과를 얻는 방법을 중심으로 설명하려 한다.
이 문제를 알고리즘적으로 분류하면 다음과 같다. 우선, 주어진 숫자들 중에서 특정 조건을 만족하는 조합을 찾는 과정이 주를 이루므로 기본적으로는 탐색 문제로 분류할 수 있다. 특히, "서로 다른 두 개의 인덱스를 골라야 한다"는 조건은 명백한 조합 탐색의 성격을 가진다. 따라서 DFS + 백트래킹(Backtracking)의 접근법을 사용할 수 있다. 또한, 최종적으로 얻은 숫자들을 오름차순으로 정렬하고 중복을 제거한다는 점에서 자료구조적으로는 집합(Set)을 활용하거나 정렬(Sorting)을 추가적으로 수행하는 과정이 필요하다.
- 탐색(DFS, Backtracking): 모든 가능한 두 숫자 조합을 탐색
- 조합(Combination): 인덱스 쌍을 선택하여 처리
- 자료구조(Set, Array): 중복 제거 및 결과 저장
- 정렬(Sorting): 결과를 오름차순으로 반환하기 위한 과정
🔎 접근
DFS + 백트래킹을 연습하기 좋은 문제다.
어떻게 DFS를 적용해볼 수 있을까? 두 가지 포인트를 고려해보아야 한다.
- 어떻게 하면 효율적으로 중복 조합을 피할 수 있을까?
- 어떤 방식으로 상태를 관리해야 DFS 탐색을 하면서 불필요한 중복이나 재탐색을 막을 수 있을까?
이번 문제는 인덱스를 기준으로 조합을 만들어야 하는 문제다. 즉, 특정 숫자를 선택했을 때 다시는 그 이전 인덱스로 돌아가거나 같은 인덱스를 반복적으로 선택하면 안 된다. 그렇다면 백트래킹을 활용해 어떤 숫자를 선택한 뒤에는 그 다음 인덱스부터만 탐색하도록 경계를 명확히 하면 어떨까 하는 아이디어를 떠올릴 수 있겠다.
또한, DFS를 사용한다고 했을 때, 선택할 숫자의 개수가 명확히 2개로 정해져 있기 때문에, 깊이가 2가 되면 즉시 숫자를 합산한 뒤 탐색을 멈추고 다시 돌아와야 한다. 탐색이 2단계에 도달하면 바로 결과를 기록하고 다시 전 단계로 돌아가 다른 선택을 시도하는 방식으로 상태를 관리하면 될 것이다.
그리고 이중 반복문 풀이 코드에서도 사용한 것 처럼 중복 제거 로직이 필요하다. 간단하게 Set 자료구조를 사용하여 처리할 수 있다. 정렬도 마찬가지로 Set에서 제공하는 기능을 사용하면 된다.
💡 풀이 코드
이제 실제 구현 코드와 흐름을 살펴보자.
먼저, 전체 코드이다.
import java.util.TreeSet
class Solution {
companion object {
lateinit var NUMBERS: IntArray // 입력 배열 저장
val SUMS: MutableSet<Int> = TreeSet() // 중복 제거 및 자동 정렬
}
private fun dfs(start: Int, depth: Int, currentSum: Int) {
if (depth == 2) { // 두 숫자를 골랐다면
SUMS.add(currentSum) // 합을 저장하고 리턴
return
}
for (i in start until NUMBERS.size) {
dfs(i + 1, depth + 1, currentSum + NUMBERS[i]) // 다음 숫자를 탐색
}
}
fun solution(numbers: IntArray): IntArray {
NUMBERS = numbers
dfs(0, 0, 0) // 탐색 시작
return SUMS.toIntArray() // 결과 배열 반환
}
}
이제 실제로 주어진 예제 입력 [2, 1, 3, 4, 1]을 통해 DFS의 호출 흐름을 따라가 보자.
예시 배열 [2, 1, 3, 4, 1] 로 본 DFS 호출
- depth: 현재 선택한 숫자 개수
- start: 선택 가능한 숫자의 인덱스 시작 위치
- currentSum: 지금까지 선택한 숫자들의 합
- SUMS: depth=2일 때 추가되는 최종 결과 저장 집합
0️⃣ 루트 호출 진입
| 시각 | 호출 | (start, depth, currentSum) | 선택한 숫자 | SUMS |
| t0 | A | (0, 0, 0) | [] | {} |
1️⃣ 루트 A의 for (i = 0~4) 진행
A: start=0, depth=0
├─ i=0 → 값 2 → 호출 B
├─ i=1 → 값 1 → 호출 F (B 종료 후)
├─ i=2 → 값 3 → 호출 I (F 종료 후)
├─ i=3 → 값 4 → 호출 L (I 종료 후)
└─ i=4 → 값 1 → 호출 O (L 종료 후)
1-1) 서브 호출 B (start=1, depth=1, sum=2, 선택한 숫자=[2])
B: for (i = 1~4)
├─ i=1 → 값 1 → C (depth=2)
├─ i=2 → 값 3 → D (depth=2)
├─ i=3 → 값 4 → E (depth=2)
└─ i=4 → 값 1 → E2 (depth=2)
| 리프호출 | 선택 | 숫자 합 | 결과(SUMS 변화) |
| C | [2, 1] | 3 | SUMS={3} 추가 |
| D | [2, 3] | 5 | SUMS={3,5} 추가 |
| E | [2, 4] | 6 | SUMS={3,5,6} 추가 |
| E2 | [2, 1] | 3 | 이미 있음 → 변화 없음 |
B 종료 후: SUMS={3,5,6}
1-2) 서브 호출 F (start=2, depth=1, sum=1, 선택한 숫자=[1])
F: for (i = 2~4)
├─ i=2 → 값 3 → G (depth=2)
├─ i=3 → 값 4 → H (depth=2)
└─ i=4 → 값 1 → H2 (depth=2)
| 리프호출 | 선택 | 숫자 합 | 결과(SUMS 변화) |
| G | [1, 3] | 4 | SUMS={3,4,5,6} 추가 |
| H | [1, 4] | 5 | 이미 있음 → 변화 없음 |
| H2 | [1, 1] | 2 | SUMS={2,3,4,5,6} 추가 |
F 종료 후: SUMS={2,3,4,5,6}
1-3) 서브 호출 I (start=3, depth=1, sum=3, 선택한 숫자=[3])
I: for (i = 3~4)
├─ i=3 → 값 4 → J (depth=2)
└─ i=4 → 값 1 → K (depth=2)
| 리프호출 | 선택 | 숫자 합 | 결과(SUMS 변화) |
| J | [3, 4] | 7 | SUMS={2,3,4,5,6,7} 추가 |
| K | [3, 1] | 4 | 이미 있음 → 변화 없음 |
I 종료 후: SUMS={2,3,4,5,6,7}
1-4) 서브 호출 L (start=4, depth=1, sum=4, 선택한 숫자=[4])
L: for (i = 4~4)
└─ i=4 → 값 1 → M (depth=2)
| 리프호출 | 선택 | 숫자 합 | 결과(SUMS 변화) |
| M | [4, 1] | 5 | 이미 있음 → 변화 없음 |
L 종료 후: SUMS={2,3,4,5,6,7}
1-5) 서브 호출 O (start=5, depth=1, sum=1, 선택한 숫자=[1])
- 여기서 start=5는 배열 크기(5)와 같으므로, 더 이상 선택할 수 없음. 즉시 종료.
2️⃣ 전체 DFS 탐색 종료 후 상태:
- 모든 재귀 호출이 종료되었고, 최종적으로 얻은 결과는 다음과 같다.
SUMS = {2, 3, 4, 5, 6, 7}
따라서 최종적으로 반환하는 값은:
[2, 3, 4, 5, 6, 7]
🚀 최종 제출 코드
자바
import java.util.*;
class Solution {
private static int[] NUMBERS;
private static final Set<Integer> SUMS = new TreeSet<>();
private void dfs(int start, int depth, int currentSum) {
if (depth == 2) { // 두 수를 골랐다면
SUMS.add(currentSum); // 합 저장
return;
}
for (int i = start; i < NUMBERS.length; i++) {
dfs(i + 1, depth + 1, currentSum + NUMBERS[i]);
}
}
public int[] solution(int[] numbers) {
NUMBERS = numbers;
dfs(0, 0, 0);
return SUMS.stream().mapToInt(Integer::intValue).toArray();
}
}
코틀린
import java.util.TreeSet
class Solution {
companion object {
// 입력 배열 (전역)
lateinit var NUMBERS: IntArray
// 중복 제거 + 오름차순 정렬용 TreeSet
val SUMS: MutableSet<Int> = TreeSet()
}
private fun dfs(start: Int, depth: Int, currentSum: Int) {
if (depth == 2) { // 두 수를 골랐다면
SUMS.add(currentSum) // 합 저장
return
}
for (i in start until NUMBERS.size) {
dfs(i + 1, depth + 1, currentSum + NUMBERS[i])
}
}
fun solution(numbers: IntArray): IntArray {
NUMBERS = numbers
dfs(0, 0, 0)
return SUMS.toIntArray()
}
}