Writer: Steven, Lee
Date: 4/2, Tuesday
Purpose: Solving #264 Ugly Number II (Dynamic Programming)
Level: Medium
Percentage: 35.8% have solved this problem
Time: it took me an 1 hour :)
Time Complexity: O(n) worst case
Runtime: 2 ms, faster than 99.71% of Java submissions
한국어 버전은 밑에 있습니다.
* Caution * Before you read the solution that I used, you need to solve this problem by yourself
* Description *
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
* Example *
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
* Note *
- 1 is typically treated as an ugly number.
- n does not exceed 1690.
* Idea *
Let's talk about this problem with a failure and simple way that anybody can find out. Firstly, we can easily understand the rule about making ugly numbers. if a given number is 7 (1 x 7), then it can not be a ugly number. Because, it's not the number whose prime facotors are part of (2, 3, 5). A given number is 14 (2 x 7), it can not be a ugly number. Because, it includes 7 out of (2, 3, 5). By the way, why we don't need to check whether 7 is a ugly number or not. Obviously, we have to do that ! What if a number is 24(2 x 14), we need to analyze 14 to check. Here 7, we've aleady checked it before 14. so here is the solution. we make a map where we are going to put ugly numbers here. Next, we divide every single numbers with 2, 3, 5. if a remainder is zero and quotient is in the map, then, it should be a ugly number that will put in the map. Here is an example for this.
map = [1]
2 ==> quot = 1 && remainder = 0 * map = [1, 2] *
3 ==> quot = 1 && remainder = 0 * map = [1, 2, 3] *
4 ==> quot = 2 && reaminder = 0 * map = [1, 2, 3, 4] *
5 ==> quot = 1 && reaminder = 0 * map = [1, 2, 3, 4, 5] *
6 ==> quot = 3 && reaminder = 0 * map = [1, 2, 3, 4, 5, 6] *
7 ==> quot = 3 && reaminder = 1 * map = [1, 2, 3, 4, 5, 6] *
*
*
14 ==> quot = 7 && remainder = 0 * map = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]
Indeed, it will be facing time limit problem :( it needs to check a quotient is in the map, it causes that time complexity should be O(n^2). but we have to solve it in O(n). I had to find an another solution and here is it. Let's make an map that we are going to put in only ugly numbers. we have 3 different options 2, 3, 5 and every single ugly numbers has to consist of these options. then, we can make ugly numbers from 1 to the target number by picking smallest combination of a number in the map and a following number step by step. Let's dive deeper into my solution with an example.
Here is the example.
1. map = [1] * nextTwo = 0, nextThree = 0, nextFive = 0 *
2. smallest = min(2 * map[nextTwo], 3 * map[nextThree], 5 * map[nextFive]) = 2
map = [1, 2] nextTwo should be increased * nextTwo = 1, nextThree = 0, nextFive = 0 *
3. smallest = min(2 * map[nextTwo], 3 * map[nextThree], 5 * map[nextFive]) = 3
map = [1, 2, 3] nextThree should be increased * nextTwo = 1, nextThree = 1, nextFive = 0 *
4. smallest = min(2 * map[nextTwo], 3 * map[nextThree], 5 * map[nextFive]) = 4
map = [1, 2, 3, 4] nextTwo should be increased * nextTwo = 2, nextThree = 1, nextFive = 0 *
5. smallest = min(2 * map[nextTwo], 3 * map[nextThree], 5 * map[nextFive]) = 5
map = [1, 2, 3, 4, 5] nextFive should be increased * nextTwo = 2, nextThree = 1, nextFive = 1 *
6. smallest = min(2 * map[nextTwo], 3 * map[nextThree], 5 * map[nextFive]) = 6
map = [1, 2, 3, 4] nextTwo should be increased * nextTwo = 3, nextThree = 1, nextFive = 1 *
7. smallest = min(2 * map[nextTwo], 3 * map[nextThree], 5 * map[nextFive]) = 8
map = [1, 2, 3, 4] nextTwo should be increased * nextTwo = 4, nextThree = 1, nextFive = 1 *
8. smallest = min(2 * map[nextTwo], 3 * map[nextThree], 5 * map[nextFive]) = 9
map = [1, 2, 3, 4] nextThree should be increased * nextTwo = 4, nextThree = 2, nextFive = 1 *
*
*
* return map[map.length-1] *
we can easily understand how to calculate smallest with an example :). The main point here is making ugly numbers step by step.
(한국어)
* 난이도: 중간 *
* 오직 35.8%만이 이 문제를 풀었습니다. *
* 저는 1시간 정도가 걸렸습니다. *
* 시간 복잡도는 O(n)입니다 *
* 런타임은 2ms로 자바로 제출한 99.71%보다 빠릅니다. *
* 주의 * 솔루션을 읽기 전에 스스로 문제를 푸실 수 있어야 합니다.
* 지문 *
n번째에 있는 못생긴 숫자를 찾는 프로그램을 작성하시오.
* 못생긴 숫자들은 소인수가 오직 2, 3, 5로 구성된 양의 정수를 의미합니다. *
* 예시 *
입력: n = 10
출력: 12
설명: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12는 10번째 못생긴 숫자가 나온 일련의 숫자들입니다.
* 주의할 점 *
- 1은 예외적으로 못생긴 숫자로 간주합니다.
- n은 1690을 넘지 않습니다.
* 아이디어 *
모든 사람들이 찾을 수 있는 쉬운 방법(정답은 아닙니다.)으로 먼저 접근해보겠습니다. 독자분들은 못생긴 숫자들을 만드는 규칙들을 쉽게 이해할 수 있을 것입니다. 만약 주어진 숫자가 7(1x7)이면 이것은 못생긴 숫자가 아닙니다. 왜냐하면 소인수가 (2, 3, 5)만으로 구성되어 있지 않기 때문입니다. 또한 주어진 숫자가 14(2x7)이면 이것도 그 숫자가 될 수 없습니다. 같은 이유로 7은 그 소인수에 해당되지 않기 때문입니다. 그런데 왜 여기서 7은 분석하지 않는 것일까요?? 확실하게 말하면 분석을 해야 합니다. 만약 숫자가 24(2x14)이면 14 또한 (2, 3, 5) 소인수를 가지는지 조사를 해봐야합니다. 그렇지만 7은 이미 14 전에 작업을 끝냈기 때문에 다시 할 필요는 없습니다. 여기서 아이디어를 얻게 됩니다. 못생긴 숫자들을 넣을 공간, 맵을 일단 만듭니다. 그런 후 모든 숫자들을 2, 3, 5로 나눠봅니다. 나머지가 0이고 몫이 그 맵안에 있을 때 그 숫자는 우리가 찾는 것이고 그 숫자를 맵에 넣고 작업을 계속 합니다. 다음은 이 해결방법에 대한 예시입니다.
map = [1]
2 ==> 몫 = 1 && 나머지 = 0 * map = [1, 2] *
3 ==> 몫 = 1 && 나머지 = 0 * map = [1, 2, 3] *
4 ==> 몫 = 2 && 나머지 = 0 * map = [1, 2, 3, 4] *
5 ==> 몫 = 1 && 나머지 = 0 * map = [1, 2, 3, 4, 5] *
6 ==> 몫 = 3 && 나머지 = 0 * map = [1, 2, 3, 4, 5, 6] *
7 ==> 몫 = 3 && 나머지 = 1 * map = [1, 2, 3, 4, 5, 6] *
*
*
14 ==> 몫 = 7 && 나머지 = 0 * map = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]
사실, 이 접근은 시간초과라는 문제점이 발생합니다. 몫이 맵안에 있는지 확인을 해야 하는데 이것이 시간복잡도를 O(n^2)으로 만듭니다. 하지만 우리들은 이 문제를 O(n)으로 풀어야 합니다. 이제 제가 찾은 다른 방법을 소개하겠습니다. 첫번째로 못생긴 숫자들만 넣을 공간 맵을 만듭니다. 그리고 우리들은 총 3가지의 다른 옵션(2, 3, 5)들이 있고 모든 숫자들은 이것으로 구성되어야 합니다. 그렇다면 1에서 부터 목표 숫자까지 맵에서 고른 숫자와 따라오는 숫자들의 조합에서 가장 작은 것을 고르는 방법으로 못생긴 숫자들을 차례대로 만들 수 있습니다. 예시와 함께 더 자세히 설명하겠습니다.
예시입니다.
1. map = [1] * nextTwo = 0, nextThree = 0, nextFive = 0 *
2. smallest = min(2 * map[nextTwo], 3 * map[nextThree], 5 * map[nextFive]) = 2
map = [1, 2] nextTwo should be increased * nextTwo = 1, nextThree = 0, nextFive = 0 *
3. smallest = min(2 * map[nextTwo], 3 * map[nextThree], 5 * map[nextFive]) = 3
map = [1, 2, 3] nextThree should be increased * nextTwo = 1, nextThree = 1, nextFive = 0 *
4. smallest = min(2 * map[nextTwo], 3 * map[nextThree], 5 * map[nextFive]) = 4
map = [1, 2, 3, 4] nextTwo should be increased * nextTwo = 2, nextThree = 1, nextFive = 0 *
5. smallest = min(2 * map[nextTwo], 3 * map[nextThree], 5 * map[nextFive]) = 5
map = [1, 2, 3, 4, 5] nextFive should be increased * nextTwo = 2, nextThree = 1, nextFive = 1 *
6. smallest = min(2 * map[nextTwo], 3 * map[nextThree], 5 * map[nextFive]) = 6
map = [1, 2, 3, 4] nextTwo should be increased * nextTwo = 3, nextThree = 1, nextFive = 1 *
7. smallest = min(2 * map[nextTwo], 3 * map[nextThree], 5 * map[nextFive]) = 8
map = [1, 2, 3, 4] nextTwo should be increased * nextTwo = 4, nextThree = 1, nextFive = 1 *
8. smallest = min(2 * map[nextTwo], 3 * map[nextThree], 5 * map[nextFive]) = 9
map = [1, 2, 3, 4] nextThree should be increased * nextTwo = 4, nextThree = 2, nextFive = 1 *
* return map[map.length-1] *
어떤 식으로 가장 작은 것을 구할 수 있는지 예시와 함께 살펴보았습니다. 핵심 포인트는 못생긴 숫자들을 차례대로 만들 수 있다는 것입니다.
* Check *
이 사이트에서 정답의 유무를 확인하실 수 있습니다.
https://leetcode.com/problems/ugly-number-ii/
public class UglyNumbers {
public static int nthUglyNumber(int N) {
int[] map = new int[N];
int n;
int nextTwo, nextThree, nextFive;
n = map[0] = 1;
nextTwo = nextThree = nextFive = 0;
for(int j = 1 ; j < N ; j++) {
int uglyNum = Math.min(2 * map[nextTwo], Math.min(3 * map[nextThree], 5 * map[nextFive]));
if(uglyNum == 2 * map[nextTwo]) {
nextTwo++;
map[n] = uglyNum;
}
if(uglyNum == 3 * map[nextThree]) {
nextThree++;
map[n] = uglyNum;
}
if(uglyNum == 5 * map[nextFive]) {
nextFive++;
map[n] = uglyNum;
}
n++;
}
return map[map.length-1];
}
public static void main(String[] args) {
int res = nthUglyNumber(10);
System.out.println("Result: " + res);
}
}'DataStructures & Algorithm (Practice)' 카테고리의 다른 글
| Google #5 Replace O's with X's (0) | 2019.04.09 |
|---|---|
| Google #4 Edit Distance (0) | 2019.04.04 |
| Google #2 Number of Islands (0) | 2019.01.27 |
| Google #1 Longest Substring with At Most Two Distinct Characters (0) | 2019.01.24 |
| Leetcode #174 Dungeon Game (0) | 2019.01.18 |
