[Java] 프로그래머스 - Level1 (없는 숫자 더하기)

없는 숫자 더하기

문제 설명

0부터 9까지의 숫자 중 일부가 들어있는 정수 배열 numbers가 주어집니다.
numbers에서 찾을 수 없는 0부터 9까지의 숫자를 모두 찾아 더한 수를 return 하도록 solution 함수를 완성하세요.

제한사항

• 1 ≤ numbers의 길이 ≤ 9
• 0 ≤ numbers의 모든 원소 ≤ 9
• numbers의 모든 원소는 서로 다릅니다.

입출력 예

numbers	result
[1,2,3,4,6,7,8,0]	14
[5,8,4,0,6,7,9]	6

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

풀이 링크
https://github.com/thezz9/codingTest/commit/b2233799efc50e4de3ba9084f82f06a54f5d3f20

---

3가지 해결 방법 & 성능 비교

나는 이 문제를 반복문을 사용해 풀었지만, 다른 방법도 찾아보니 여러 가지가 있어서 비교하는 글을 작성해보려고 한다.
배열에서 0~9 범위 내에서 존재하지 않는 숫자만 더하는 방법을 3가지로 구현하고 성능을 비교해보자.

1. 반복문 + 조건문 활용

코드 구현

class Solution {
    public int solution(int[] numbers) {
        int answer = 0;
        
        for (int i = 0; i <= 9; i++) { // 0부터 9까지 확인
            boolean exists = false;
            
            for (int num : numbers) { // 배열을 순회하며 존재 여부 확인
                if (num == i) {
                    exists = true;
                    break;
                }
            }
            
            if (!exists) { // 존재하지 않을 때만 더하기
                answer += i;
            }
        }
        
        return answer;
    }
}

설명

• for 문을 사용해 0부터 9까지 순회
• numbers 배열을 내부 for 문으로 확인하면서 숫자가 있으면 break
• 배열에 존재하지 않는 숫자만 answer에 더함

시간 복잡도

• O(n * m) (n = 배열 크기, m = 범위 크기)
• 배열이 클수록 성능이 떨어짐

---

2. HashSet 활용 (빠른 조회)

코드 구현

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int solution(int[] numbers) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : numbers) {
            numSet.add(num);
        }

        int answer = 0;
        for (int i = 0; i <= 9; i++) {
            if (!numSet.contains(i)) { // HashSet에서 O(1)로 빠르게 존재 여부 체크
                answer += i;
            }
        }

        return answer;
    }
}

설명

• numbers 배열을 HashSet으로 변환 (O(n))
• for 문을 돌면서 HashSet.contains()를 사용해 존재 여부 확인 (O(1))
• 존재하지 않는 숫자만 answer에 더함

시간 복잡도

• O(n + m) (n = 배열 크기, m = 범위 크기)
• HashSet을 생성하는 데 O(n), 존재 여부를 체크하는 데 O(1)
• 배열 크기가 커질수록 성능이 훨씬 좋음

---

3. Stream API 활용 (HashSet 없이)

코드 구현

import java.util.Arrays;
import java.util.stream.IntStream;

class Solution {
    public int solution(int[] numbers) {
        return IntStream.rangeClosed(0, 9) // 0부터 9까지 순회
                .filter(num -> Arrays.stream(numbers).noneMatch(n -> n == num)) // numbers에 없는 숫자만 필터링
                .sum(); // 합산
    }
}

설명

• IntStream.rangeClosed(0, 9)으로 0부터 9까지의 숫자를 생성
• filter()에서 Arrays.stream(numbers).noneMatch(n -> n == num)로 배열에 없는 숫자만 필터링
• 최종적으로 .sum()을 사용하여 합산

시간 복잡도

• O(n * m) (m = 범위 크기, n = 배열 크기)
• noneMatch()가 내부적으로 배열을 순회 (O(n)) 하기 때문에 반복문과 성능이 비슷

---

성능 비교 (배열 크기별 테스트)

방법	시간 복잡도	작은 배열 (n=5)	큰 배열 (n=1000)	특징
반복문 + 조건문	O(n * m)	빠름	느림	단순한 로직이지만 배열이 크면 성능 저하
HashSet 활용	O(n + m)	빠름	매우 빠름	HashSet을 사용해 존재 여부를 빠르게 확인
Stream API (noneMatch)	O(n * m)	빠름	느림	noneMatch()가 배열을 계속 탐색하므로 성능 저하

---

결론 및 추천

성능이 중요하면? → HashSet 활용 (O(n + m), 빠름)
코드가 간결한 게 중요하면? → Stream API (O(n * m), 가독성 좋음)
그냥 가장 쉬운 방법? → 반복문 + 조건문 (O(n * m), 이해하기 쉬움)

배열이 작으면 차이가 크지 않지만, 크다면 HashSet을 적극 활용하자.