소인수가 2, 3, 5뿐인 수를 '못생긴 숫자(Ugly Number)'라고 부릅니다. 예를 들어 못생긴 숫자의 나열은 다음과 같습니다.
1, 2, 3, 4, 5, 6, 8, 10, 12, 15, ...
이번 글에서는 숫자 N이 주어졌을 때, 위 수열에서 N번째에 해당하는 못생긴 숫자를 찾는 방법을 자바 코드와 함께 알아보겠습니다.
문제 이해하기
예제를 통해 문제를 살펴보겠습니다.
입력 예시 1:
N = 5
출력:
5
설명: 못생긴 숫자 수열 [1, 2, 3, 4, 5, 6, 8, 10, 12, 15]에서 5번째 숫자는 5입니다.
입력 예시 2:
N = 7
출력:
8
설명: 같은 수열에서 7번째 숫자는 8입니다. 참고로 7은 소인수로 7을 가지므로 못생긴 숫자가 아니며, 수열에서 건너뛰게 됩니다.
해결 접근 방법
가장 직관적인 방법은 각 숫자가 2, 3, 5로만 나누어지는지 하나씩 검사하면서, 조건을 만족하는 숫자를 세어나가는 것입니다.
- N번째 못생긴 숫자를 찾기 위해 정수 N을 입력받습니다.
- Boolean 타입의 함수
isUglyNumber(int num)는 입력된 수가 못생긴 숫자이면 true를, 그렇지 않으면 false를 반환합니다. - 정수형 함수
nthUglyNumber(int n)는 n을 입력받아 n번째 못생긴 숫자를 반환합니다.
자바 코드 구현
public class UglyN {
public static boolean isUglyNumber(int num) {
boolean x = true;
while (num != 1) {
if (num % 5 == 0) {
num /= 5;
}
else if (num % 3 == 0) {
num /= 3;
}
// 2로 나누어 떨어지는지 확인
else if (num % 2 == 0) {
num /= 2;
}
else {
x = false;
break;
}
}
return x;
}
public static int nthUglyNumber(int n) {
int i = 1;
int count = 1; // 1은 항상 첫 번째 못생긴 숫자
while (n > count) {
i++;
if (isUglyNumber(i)) {
count++;
}
}
return i;
}
public static void main(String[] args) {
int number = 100;
int no = nthUglyNumber(number);
System.out.println("The Ugly no. at position " + number + " is " + no);
}
}실행 결과
The Ugly no. at position 100 is 1536.
코드 동작 원리
isUglyNumber() 메서드는 입력값을 반복적으로 5, 3, 2 순서로 나누어 떨어지면 계속 나눕니다. 만약 어느 것으로도 나누어 떨어지지 않으면서 값이 1이 되지 않는다면, 그 수에는 2, 3, 5 이외의 소인수가 존재한다는 의미이므로 false를 반환합니다.
nthUglyNumber() 메서드는 1부터 시작하여 숫자를 하나씩 증가시키면서 각 숫자가 못생긴 숫자인지 검사하고, 못생긴 숫자를 발견할 때마다 카운트를 늘립니다. 카운트가 N에 도달하면 해당 숫자를 결과로 반환합니다.
마치며
위 방법은 이해하기 쉽지만, N이 커질수록 모든 숫자를 일일이 검사해야 하므로 시간이 오래 걸릴 수 있습니다. 성능이 중요한 경우에는 동적 프로그래밍(DP) 방식으로 이미 찾은 못생긴 숫자들에 2, 3, 5를 곱해 다음 숫자를 생성하면 훨씬 빠르게 답을 구할 수 있습니다.