uglyNumber란, 2, 3, 5 로만 나누어 떨어지는 수를 뜻한다.
예를 들어, uglyNumber에는 1,2,3,4,5,6,8,9,10... 등이 있다.
문제
인덱스 n을 입력받아, n번째 uglyNumber를 반환해야 한다.
단순히 1부터 차례대로 uglyNumber를 구해 count를 추가해가면서 구할 수도 있겠지만, 문제를 O(N) 의 시간복잡도로 풀 수 있는 방법이 존재했다.
풀이
위의 풀이에서
int multipledBy2 = uglyNumbers.get(idx2) * 2;
int multipledBy3 = uglyNumbers.get(idx3) * 3;
int multipledBy5 = uglyNumbers.get(idx5) * 5;
int nextUglyNumber = Math.min(Math.min(multipledBy2, multipledBy3), multipledBy5);
uglyNumbers.add(nextUglyNumber);이 부분을 for문의 진행에 따라 차례대로 계산해보면,
uglyNumbers =[1], idx2 = 0, idx3 = 0, idx5 = 0
uglyNumbers =[1, 2] idx2 = 1, idx3 = 1, idx5 = 0
uglyNumbers =[1,2,3] idx2 = 1, idx3 = 1, idx5 = 1
uglyNumbers =[1,2,3,5] idx2 = 1, idx3 = 1, idx5 = 1
uglyNumbers =[1,2,3,4,5] idx2 = 2, idx3 = 1, idx5 = 1
순으로 진행될 것이고, uglyNumbers에 6을 추가해줄때는 2 x 3과 3 x 2 로 중복되고, 후에 다시 uglyNumbers에 6을 추가해서는 안되기 때문에 아래에 작성된 조건문에 따라 idx2와 idx3의 값을 모두 증가시켜주기 때문에,
uglyNumbers =[1,2,3,4,5,6], idx2 = 3, idx3 = 2, idx5 = 1
의 형태가 될 것이다.
결국 1부터 차례로 모든 수를 검증하지 않고, 더 짧은 시간 안에 주어진 index의 uglyNumber를 구할 수 있게 된다.
