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

📑 1. 문제설명

---

💡 2. 풀이과정

이건 이중 for문 + Set + 정렬 문제이다.

입출력예에서 중복값이 없기 때문에 중복을 허용하지 않는 자료형 해시셋을 사용해서 푼다. 

1. 배열에서 이중 포문을 사용해서 두 수를 선택하는 모든 경우의 수를 구한다.

2. 위에서 구한 수를 더해서 해시셋에 추가해서 중복제거한다.

3. 해시셋 값을 오름차순 정렬한다.

4. int[] 형태의 배열로 변환해서 반환한다. 이 때 stream을 사용한다.

---

👨‍💻 3. 정답코드

처음에 이중 for문의 범위를 잘못 잡았는데, 바깥 for문의 i 범위를 `i < numbers.length` 까지로 잡았었다.
이렇게 하면 노노❌

 

왜냐하면 바깥 for문에서 i < numbers.length - 1이라면 안쪽 for문의 j = i + 1 = numbers.length가 되는데,
이 경우 j < numbers.length 조건이 바로 false가 되어 안쪽 for문이 한 번도 실행되지 않는다.

결국 바깥 for문 마지막 반복 (i == 마지막 인덱스)에서는 j가 더할 상대가 없기 때문에

쓸모 없는 반복이 한 번 일어나는 셈이고 그래서 바깥 for문은 `i < numbers.length - 1` 까지로 잡는다.

import java.util.HashSet;

class Solution {
    public int[] solution(int[] numbers) {
        HashSet<Integer> answer = new HashSet<>(); // 중복 제거용 해시셋
        for (int i = 0; i < numbers.length - 1; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                answer.add(numbers[i] + numbers[j]);
            } 
        }
        return answer.stream().sorted().mapToInt(Integer::intValue).toArray();
    }
}

문제를 다 풀고 다른 사람들은 어떻게 풀었나 보니까 다들 비슷한 방식으로 풀었다.

HashSet보다 TreeSet이 더 빠르고 add할 때 자동으로 정렬이 된다고 하는 사람들도 있었으나

그렇지 않고 데이터가 많아질수록 HashSet이 훨씬 빠르다. 

 

시간복잡도

이중포문이 나오면 시간 복잡도가 O(N^2)이다. 

정렬 알고리즘 대부분은 O(N log N)의 시간 복잡도를 가진다. 

 

Set에 있는 최대 N²개의 데이터를 정렬하면 O(N² log N²) = O(N² log N)이다.
Big-O 표기에서는 상수 계수는 무시하기 때문에, log N² = 2 log N이니까 결국 log N으로 간주

O(N² log N²)를 변형하는 과정은 아래와 같다.

O(N² log N²)
→ O(N² * log(N²))
→ O(N² * 2 * log(N))      ← 로그 성질 사용
→ O(2 * N² * log(N))
→ O(N² log N)              ← 상수는 생략

 

💡 `log N²` vs `log² N` 헷갈리지 말자.

log N²	2log⁡N → log가 N²에 걸림
(log N)² = log² N	(log⁡N)^2= → 로그값 자체를 제곱