문제 설명
주어진 수 N이 있을 때, N을 수의 자릿수의 합이 N보다 작도록 변환할 수 있는 컴퓨터 프로그램을 작성하시오.
여기서, 수의 자릿수의 합이 N보다 작으면 그 수를 ‘좋은 수’라고 부릅니다.
즉, 주어진 N보다 작은 모든 수 중에서 자릿수의 합이 N보다 작으면서, 가장 큰 수를 찾는 알고리즘 문제입니다.
문제 예시
예를 들어, N이 23일 경우:
- 22 (2 + 2 = 4) → ‘좋은 수’
- 21 (2 + 1 = 3) → ‘좋은 수’
- 20 (2 + 0 = 2) → ‘좋은 수’
- 19 (1 + 9 = 10) → ‘좋은 수’
- 18 (1 + 8 = 9) → ‘좋은 수’
- 17 (1 + 7 = 8) → ‘좋은 수’
- 16 (1 + 6 = 7) → ‘좋은 수’
- 15 (1 + 5 = 6) → ‘좋은 수’
- 14 (1 + 4 = 5) → ‘좋은 수’
- 13 (1 + 3 = 4) → ‘좋은 수’
- 12 (1 + 2 = 3) → ‘좋은 수’
- 11 (1 + 1 = 2) → ‘좋은 수’
- 10 (1 + 0 = 1) → ‘좋은 수’
- 9 (9 = 9) → ‘좋은 수’
가장 큰 ‘좋은 수’는 22입니다.
문제 해결을 위한 접근 방법
이 문제를 해결하기 위해 먼저, 입력으로 주어진 N보다 1 작은 수부터 내려가며 각 수의 자릿수의 합을 계산합니다.
해당 자릿수의 합이 N보다 작을 경우, 그 수를 결과로 반환하고 알고리즘을 종료하는 방식입니다.
알고리즘 구현
public class GoodNumber {
public static void main(String[] args) {
int N = 23; // 여기에서 테스트할 N 값을 설정합니다.
int result = findGoodNumber(N);
System.out.println("‘좋은 수’는: " + result);
}
public static int findGoodNumber(int N) {
for (int i = N - 1; i > 0; i--) {
if (digitSum(i) < N) {
return i; // 가장 큰 ‘좋은 수’를 반환
}
}
return -1; // 만약 찾지 못하면 -1 반환
}
public static int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10; // 각 자릿수를 더함
num /= 10; // 10으로 나누어 자릿수를 줄임
}
return sum;
}
}
코드 설명
위의 자바 코드에서는 메인 메소드에서 N값을 설정한 후, findGoodNumber 메소드를 호출하여 ‘좋은 수’를 찾아냅니다.
findGoodNumber 메소드는 N보다 1 작은 수부터 시작하여 자릿수의 합을 계산하고, 그 값이 N보다 작으면 그 수를 반환합니다.
digitSum 메소드는 주어진 숫자의 각 자릿수의 합을 계산하는 로직을 포함하고 있습니다.
이 메소드는 반복문을 사용하여 자릿수를 하나씩 분리하고 더한 결과를 반환합니다.
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 O(N * D)입니다. 여기서 N은 입력값, D는 N의 자릿수입니다.
각 수에 대해 자릿수를 sum하는 데 O(D)의 연산이 필요하게 되며, N까지 내려가며 반복하기 때문에 최악의 경우 O(N * D)의 시간 복잡도를 가집니다.
공간 복잡도
공간 복잡도는 O(1)입니다. 추가적인 공간을 사용하지 않고, 입출력 변수들과 메소드 내부의 상수적인 공간만 사용하므로
사용되는 메모리는 최소화되어 있습니다.
결론 및 팁
‘좋은 수’ 구하기 문제는 단순한 반복문과 자릿수 합 과정을 통해 그 해를 쉽게 찾을 수 있습니다.
그러나 N의 크기가 매우 클 경우 성능 저하가 우려되므로 알고리즘 최적화가 필요할 수 있습니다.
다양한 입력값에 대해 테스트 해보며, 다른 방법이나 구조로 이 문제를 해결해보는 것도 좋은 학습이 될 것입니다.
마지막으로, 코딩테스트를 준비하면서 이러한 문제를 충분히 연습해보는 것이 중요합니다.
매번 새로운 문제에 도전하며 다양한 사고력을 기르는 것은 취업 준비에 큰 도움이 될 것입니다.