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

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

 

접근 방식

1. 서로 다른 조합을 만들기 위해 numbers[i], numbers[j] 이중 for문 사용
   • j를 항상 i + 1에서 시작하도록 설정하여 같은 인덱스를 두 번 선택하는 경우(i == j)를 막고
     (a, b)와 (b, a)처럼 순서만 다른 중복 조합이 생성되지 않도록 처리 
2. 생성된 합은 Set에 넣어 중복 제거
3.  Set에 모인 값들을 꺼내 오름차순 정렬된 int 배열로 변환하여 반환

나의 풀이 코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int numberCount = numbers.length;

        HashSet<Integer> numberSet = new HashSet<>();

        for (int i = 0; i < numberCount; i++) {
            for (int j = i + 1; j < numberCount ; j++) {
                int sum = numbers[i] + numbers[j];
                numberSet.add(sum);
            }
        }

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

 

리팩토링 코드

TreeSet 사용

import java.util.Set;
import java.util.TreeSet;

class Solution {
    public int[] solution(int[] numbers) {
        int n = numbers.length;
        Set<Integer> sums = new TreeSet<>(); // 정렬 + 중복 제거

        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) { // 서로 다른 인덱스 조합
                sums.add(numbers[i] + numbers[j]);
            }
        }

        // TreeSet은 이미 오름차순 정렬 상태이므로 바로 배열로 변환
        return sums.stream()
                   .mapToInt(Integer::intValue)
                   .toArray();
    }
}

 

TreeSet vs HashSet 비교

	HashSet	TreeSet
내부 구조	해시 테이블	균형 이진 탐색 트리 (Red-Black Tree)
원소 순서	없음 (삽입 순서/정렬 보장 X)	정렬된 상태 유지 (기본 오름차순)
add / contains / remove 평균 시간	O(1)	O(log n)
정렬 필요 여부	나중에 따로 sort 필요	이미 정렬되어 있음
사용 목적	빠른 조회/삽입/삭제 (순서 상관 X)	정렬 + 범위 검색 등 순서가 중요한 경우

 

해당 문제에서는 시간 복잡도는 둘 다 O(k log k)로 이론상 동일이고 입력 크기가 작아서 체감 성능도 거의 차이 없다.

코드 직관성이나 취향에 따라 HashSet + sorted() 이나 TreeSet 한방에 정렬 둘 중 골라 사용하면 됨!