264. Ugly Number II
1) Original Idea
1부터 하나씩 ugly number인지 확인 후, n번째 ugly number를 return 한다.
: 시간이 너무 많이 걸림 & 중복연산이 너무 많음 -> 시간 초과
2) ugly number list를 저장해두고,
2, 3, 혹은 5로 나눠지는 경우(나머지가 0), 나눠진 몫이 ugly number 리스트에 있으면,
해당 number를 ugly number 리스트에 새로 추가해준다. 아니면 pass
: 해야하는 나머지 연산, 나누기 연산이 너무 많음 -> 시간 초과
3) num을 1부터 확인하지 않고, sorted map을 이용해서, map 안에 있는 것 중 ct 번째로 큰 숫자를 가져온다. 그 숫자에 2, 3, 5를 곱한 결과를 map에 넣는다. 이를 n번 반복한다. O(n)
4) 생각해보니 map을 굳이 쓸 필요가 없어서, sorted set으로 바꿨다.
5) Ultimite Solution의 등장 !
가장 작은 2의 배수, 3의 배수, 5의 배수를 유지하고, 세개의 Index 를 따로 유지해준다.
Min(2의배수, 3의배수, 5의 배수)가 ugly list에 들어갈 때,
2의 배수가 들어갔으면 다음 가장 작은 2의 배수를 (ugly_list[i2]*2)로 업데이트 해주고, i2 인덱스를 increment한다.
만약 num가 2와 5의 공통 배수라면, 2와 5의 배수 변수 둘다 업데이트 해준다.
