02-2. 두 개 뽑아서 더하기 (프로그래머스, JAVA)

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

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/68644

 

배열에서 서로 다른 두 인덱스의 값을 더한 결과를 구하고, 중복을 제거한 뒤 오름차순으로 정렬하여 반환하는 문제이다.

---

🧠 풀이 과정

1️⃣ 문제 분석

문제의 핵심 조건

• 서로 다른 인덱스의 두 수를 선택
• 두 수의 합을 모두 구하기
• 중복 제거
• 오름차순 정렬

예시

numbers = [2,1,3,4,1]

가능한 합

2+1
2+3
2+4
2+1
1+3
1+4
1+1
...

두 수의 조합 개수

n(n-1)/2

---

2️⃣ 접근 방식

✔ 이중 반복문

두 개의 인덱스를 선택하기 위해 이중 반복문을 사용한다.

for(int i = 0; i < numbers.length - 1; i++){
    for(int j = i + 1; j < numbers.length; j++){

이렇게 하면 i, j 조합이 생성되고

(i, j)

• 같은 인덱스 사용 방지 가능
• 중복 조합 방지 가능

 

---

✔ 중복 제거 방법

중복 제거 방법은 크게 2가지가 있다.

방법 1. List + contains()

• 리스트에 값이 이미 존재하면 추가하지 않음

if(!list.contains(sum)){
    list.add(sum);
}

하지만 contains()는 내부적으로 O(n) 탐색이기 때문에 데이터가 많아질수록 성능이 떨어질 수 있다.

---

방법 2. HashSet 

HashSet은 중복을 자동으로 제거한다.

이미 존재하는 값이면 자동 무시.

set.add(value)

 

시간복잡도

O(1)

---

3️⃣ 알고리즘 설계

전체 흐름

1. 두 수의 합 구하기
2. 중복 제거
3. 정렬
4. 배열 반환

---

💻 풀이 1 — List 활용

import java.util.*;

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

        // 결과 저장 리스트
        List<Integer> list = new ArrayList<>();

        // 두 수의 합 계산
        for(int i = 0; i < numbers.length - 1; i++){
            for(int j = i + 1; j < numbers.length; j++){

                int sum = numbers[i] + numbers[j];

                // 중복 체크
                if(!list.contains(sum)){
                    list.add(sum);
                }
            }
        }

        // List → 배열 변환
        int[] ans = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            ans[i] = list.get(i);
        }

        // 정렬
        Arrays.sort(ans);

        return ans;
    }
}

---

💻 풀이 2 — HashSet 활용

중복 제거를 위해 HashSet을 사용한다.

import java.util.*;

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

        // 중복 제거를 위한 HashSet
        HashSet<Integer> set = new HashSet<>();

        // 두 수의 합 구하기
        for(int i = 0; i < numbers.length - 1; i++){
            for(int j = i + 1; j < numbers.length; j++){
                set.add(numbers[i] + numbers[j]);
            }
        }

        // Set → 정렬 → 배열 변환
        return set.stream()
                .sorted()
                .mapToInt(Integer::intValue)
                .toArray();
    }
}

 

---

⏱ 시간복잡도

이중 반복문

O(n²)

정렬

O(n log n)

전체 시간복잡도

O(n²)

(이중 반복문이 가장 큰 영향)

---

🚀 정리

1️⃣ 두 수의 조합 만들기 - 이중 반복

for(int i = 0; i < n; i++)
    for(int j = i+1; j < n; j++)

 

2️⃣ 중복 제거

1. List + contains
2. HashSet

 

3️⃣ 컬렉션 → 배열 변환

set.stream()
   .sorted()
   .mapToInt(Integer::intValue)
   .toArray();