문제
정수 배열 numbers가 주어질 때, 서로 다른 인덱스에 있는 두 수를 뽑아 더해서 만들 수 있는 모든 값을 중복 없이 오름차순으로 반환한다.
numbers길이: 2 이상 100 이하numbers의 모든 수: 0 이상 100 이하
입력: [2,1,3,4,1] → 출력: [2,3,4,5,6,7]
입력: [5,0,2,7] → 출력: [2,5,7,9,12]접근 방법
처음 잡은 방향은 단순했다.
- 서로 다른 인덱스 쌍 (i, j)을 전부 뽑아서 더한다 → 브루트포스
- 합들 중 중복을 제거한다 →
HashSet에 다 넣기 HashSet을 배열로 꺼내서 오름차순 정렬한다 →Arrays.sort
여기까지는 방향이 바로 잡혔는데, 세부적으로 들어가니 걸리는 부분이 몇 개 있었다.
막혔던 부분들
1) 이중 for문에서 인덱스 범위를 어떻게 잡을 것인가
처음엔 for(i...) for(j...)를 그냥 0부터 돌리려고 했다. 그러면 두 가지 문제가 생긴다.
i == j인 경우 (같은 원소를 자기 자신과 더하는 경우)를 걸러야 함(i, j)와(j, i)를 둘 다 계산하면 같은 합을 두 번 만드는 중복 계산이 생김 (물론 어차피HashSet으로 중복 제거는 되지만, 불필요한 연산이 두 배로 늘어남)
→ j를 i+1부터 시작하면 두 문제가 한 번에 해결된다는 걸 확인.
for (int i = 0; i < numbers.length; i++) {
for (int j = i + 1; j < numbers.length; j++) {
...
}
}개수 세다가 또 헷갈린 부분: i=0일 때 j가 1부터 n-1까지 도는데, 이게 몇 번 도는지 세다가 n-2라고 착각했다. n=5로 직접 손으로 나열해보니 1,2,3,4 4개, 즉 n-1개였다. "개수 = 끝 인덱스 - 시작 인덱스 + 1" 공식을 쓰면 헷갈리지 않는다는 걸 배웠다 (인덱스 자체와 개수를 혼동하지 않기).
2) HashSet를 int[]로 어떻게 바꾸나
Set은 제네릭 컬렉션이라 기본 타입(int)을 못 담고 래퍼 타입(Integer)만 담을 수 있다. 그래서 최종 리턴 타입인 int[]로 바꾸려면 언박싱 과정이 필요했다.
Iterator<Integer>로 꺼내면서 int 변수에 대입하는 순간 자동 언박싱이 일어난다는 걸 이용해서 배열을 채웠다.
Iterator<Integer> its = sets.iterator();
int[] answer = new int[sets.size()];
int cnt = 0;
while (its.hasNext()) {
answer[cnt] = its.next(); // Integer -> int 자동 언박싱
cnt++;
}참고로 for (int num : sets) 향상된 for문도 결과는 똑같다. 이건 컴파일러가 내부적으로 iterator() / hasNext() / next() 호출로 풀어써주는 문법 설탕이라, 직접 Iterator를 쓴 코드와 완전히 동일하게 동작한다.
3) Arrays.sort — 프리미티브용과 Object용이 다르다
Arrays.sort(int[])와 Arrays.sort(Object[])(→ Integer[]에 적용)는 내부 알고리즘 자체가 다르다.
| 대상 | 알고리즘 | 기준 |
|---|---|---|
int[] | Dual-Pivot Quicksort | 값 자체 비교 |
Object[] (Integer[] 등) | TimSort (병합정렬 변형) | Comparable.compareTo() |
Integer가 Comparable<Integer>를 구현하고 있어서 Object[]용 sort도 자연스럽게 오름차순으로 동작한다. 이번 코드는 int[]에 정렬을 걸었으니 Dual-Pivot Quicksort가 쓰인 것. 둘 다 기본은 오름차순이다.
4) 시간복잡도 계산할 때 sort 단계를 빼먹었다
처음엔 "이중포문이 O(n²)이니까 전체도 O(n²)"이라고 생각했는데, 정렬 단계를 빼먹은 실수였다.
- 합을 만드는 이중포문: O(n²)
answer배열 최대 크기 m: 서로 다른 인덱스 쌍의 개수, 즉 조합nC2 = n(n-1)/2→ O(n²)- 정렬: O(m log m) = O(n² log(n²)) = O(n² log n)
두 단계는 순차 실행이므로 전체 복잡도는 더한 값이 되고, 여러 항 중에서는 가장 빨리 증가하는 항만 남는다 (상수라서 버리는 게 아니라 더 작게 증가해서 버려지는 것). O(n²) vs O(n² log n)을 더하면 log n이 붙은 쪽이 지배항이 되어 최종 복잡도는
O(n² log n)
n ≤ 100 제약이라 실제로는 10000 * log(10000) ≈ 130,000 수준이라 여유 있게 통과.
5) Set과 HashSet은 뭐가 다른가
Set: 인터페이스. "중복 허용 안 함"이라는 규약만 정의HashSet:Set을 구현한 클래스. 내부적으로HashMap을 사용 (값은 key로, 더미 값은 value로)
구현체별 성능 차이도 정리:
| 구현체 | 특징 | 평균 시간복잡도 |
|---|---|---|
HashSet | 순서 보장 X | O(1) |
LinkedHashSet | 삽입 순서 유지 (연결리스트 오버헤드) | O(1), HashSet보단 약간 느림 |
TreeSet | 정렬 순서 유지 (레드-블랙 트리) | O(log n) |
변수는 HashSet<Integer> 대신 Set<Integer>로 선언하는 게 낫다는 것도 배웠다. 실제 객체는 동일한 HashSet 인스턴스라 속도 차이는 없지만, 나중에 구현체를 TreeSet 등으로 바꿔야 할 때 선언부 타입은 그대로 두고 new 부분만 바꾸면 되는 유지보수 이점이 있다.
최종 코드
import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;
class Solution {
public int[] solution(int[] numbers) {
Set<Integer> sets = new HashSet<>();
for (int i = 0; i < numbers.length; i++) {
for (int j = i + 1; j < numbers.length; j++) {
sets.add(numbers[i] + numbers[j]);
}
}
int[] answer = new int[sets.size()];
int cnt = 0;
for (int num : sets) {
answer[cnt++] = num;
}
Arrays.sort(answer);
return answer;
}
}- 시간복잡도: O(n² log n)
- 공간복잡도: O(n²) (HashSet + 결과 배열)
회고
- 이중포문에서 인덱스 시작점을
i+1로 잡는 이유(중복 쌍 방지)는 바로 이해했는데, "몇 번 도는지" 세는 과정에서 개수와 인덱스를 혼동하는 실수를 했다. 작은 예시(n=5)로 직접 나열해서 세어보는 습관을 들이기로 함. - 시간복잡도를 구할 때 "제일 무거운 연산 하나"만 보고 끝내지 말고, 모든 단계(반복문 + 자료구조 연산 + 정렬)를 빠짐없이 더해서 지배항을 찾는 순서로 접근해야 한다는 걸 다시 확인.
HashSet,Iterator,Arrays.sort모두 그냥 쓰던 도구였는데, "왜 이렇게 동작하는지"(내부 자료구조, 알고리즘, 오토박싱/언박싱)까지 짚어보니 다음에 비슷한 문제에서 더 자신 있게 선택할 수 있을 것 같다.
