[프로그래머스] 하샤드 수

하샤드 수 판별 알고리즘 심층 분석: 두 가지 접근법 비교 및 복잡도 분석

문제 설명

양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다. 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수입니다. 자연수 x를 입력받아 x가 하샤드 수인지 아닌지 검사하는 함수, solution을 완성해주세요.

제한 조건

• x는 1 이상, 10000 이하인 정수입니다.

해결 방법

1. 반복문을 이용한 직관적인 구현

class Solution {
    public boolean solution(int x) {
        int sum = 0, n = x;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return x % sum == 0;
    }
}

• 핵심 아이디어:
  • 입력받은 수를 반복적으로 10으로 나누어 나머지를 더하여 자릿수의 합을 구합니다.
  • 최종적으로 입력받은 수를 자릿수의 합으로 나누어 떨어지는지 확인합니다.
• 장점:
  • 직관적이고 효율적이며 메모리 효율적입니다.
• 단점:
  • Java 8 Stream API를 활용하지 못한다는 점에서 아쉬울 수 있습니다.
• 시간 복잡도: O(log x) - 숫자의 자릿수만큼 반복하기 때문에 입력값 x의 크기에 따라 로그 시간이 걸립니다.
• 공간 복잡도: O(1) - 추가적인 메모리 공간을 거의 사용하지 않습니다.

2. Stream API를 이용한 간결한 구현

class Solution {
    public boolean solution(int x) {
        int total = Arrays.stream(String.valueOf(x).split(""))
                         .mapToInt(Integer::parseInt)
                         .sum();
        return x % total == 0;
    }
}

• 핵심 아이디어:
  • 숫자를 문자열로 변환하여 각 자릿수를 분리하고, Stream API를 이용하여 각 자릿수를 정수로 변환한 후 합계를 구합니다.
• 장점:
  • 간결하고 함수형 프로그래밍 스타일을 경험할 수 있습니다.
• 단점:
  • 성능 저하: 문자열 변환, 스트림 생성, 박싱/언박싱 등의 과정에서 오버헤드가 발생하여 성능이 저하될 수 있습니다.
  • 복잡성: Stream API에 익숙하지 않은 경우 코드 이해가 어려울 수 있습니다.
• 시간 복잡도: O(log x) - 숫자의 자릿수만큼 반복하는 내부 로직은 동일하지만, 스트림 처리 과정에서 추가적인 오버헤드가 발생할 수 있습니다.
• 공간 복잡도: O(log x) - 스트림 생성 및 중간 결과 저장에 필요한 메모리 공간이 발생할 수 있습니다.

두 코드 비교 및 결론

비교 항목	반복문	Stream API
성능	우수	상대적으로 느림
가독성	직관적	함축적
메모리 사용량	적음	상대적으로 많음
코드 길이	길음	짧음
시간 복잡도	O(log x)	O(log x) (상수배 오버헤드)
공간 복잡도	O(1)	O(log x)

결론:

일반적으로 반복문을 이용한 방식이 성능 면에서 우수하고 메모리 효율적입니다. 특히, 큰 숫자를 다루거나 성능이 중요한 경우에는 반복문 방식을 선택하는 것이 좋습니다. 하지만 코드의 가독성을 중요하게 생각하거나 Java 8의 Stream API를 활용하고 싶다면 Stream API 방식을 사용할 수 있습니다.