leetcode 263(ugly num), 264(ugly num2), 313

263 https://leetcode.com/problems/ugly-number/

ugly한 숫자란 2,3,5로만 나눴을때 나누어 떨어지는 수이다. ugly한 숫자인지 체크하자.

class Solution(object):
    def isUgly(self, num):
        if num == 0:
            return False
        
        for p in [2, 3, 5]:
            while True:
                if num%p == 0:  # num이 2,3,5중 하나로 나누어지면 안 나눠질때까지 계속 나눔.
                    num /= p
                    continue
                break
            
        return num == 1  # 1이 나오면 ugly한 숫자, 아니면 ㄴㄴ

264 https://leetcode.com/problems/ugly-number-ii/

n번째 ugly number를 구하는 문제이다. 처음엔 dfs로 풀었는데 시간이 너무 오래 걸린다. 2024ms.

from collections import deque
class Solution(object):
    def nthUglyNumber(self, n):
        #n = 1690
        def get_ugly():
            ret = []
            ret_len = 0
            ugly_list = [2, 3, 5]
            queue = deque([1, 2, 3, 5])
            visited = set([1, 2, 3, 5])
            while queue:
                p = queue.popleft()
                ret.append(p)
                ret_len += 1
                for ugly in ugly_list:
                    next = p * ugly
                    if next not in visited and ret_len < 4500:  # 대략 4500까지하면 1690개를 구할수 있음..
                        visited.add(next)
                        queue.append(next)
            return sorted(ret)
        
        ugly = get_ugly()
        #print n,ugly
        return ugly[n-1]

그래서 개선점을 생각해보니 쓸때없이 4500개까지 구하면 안되고 현재 있는 ugly list중 가장 낮은 숫자 기준으로 다음 ugly number를 구해야한다. 큐 대신 heap을 사용해서 매번 들어오는 값을 정렬한 후 heappop으로 큐에서 현재 있는 수중 가장 낮은 수를 리턴하도록 했다. 그러니 536ms까지 떨어졌다.

from heapq import *
class Solution(object):
    def nthUglyNumber(self, n):
        #n = 1690
        def get_ugly():
            ret = []
            ret_len = 0
            queue = [1, 2, 3, 5]
            heapify(queue)
            visited = set([1, 2, 3, 5])
            while queue:
                p = heappop(queue)
                ret.append(p)
                ret_len += 1
                for ugly in [2, 3, 5]:
                    next = p * ugly
                    if next not in visited and ret_len < n:
                        visited.add(next)
                        heappush(queue, next)
            return sorted(ret)
        
        ugly = get_ugly()
        #print n,ugly
        return ugly[n-1]

근데 가장 빠른 답들을 보니 dfs방식이 아니라 dp로 피보나치수열 구하듯이 가장 낮은 ugly number를 유지해주면서 값을 구하니 훨씬 빠르다.

class Solution(object):
    def nthUglyNumber(self, n):
        ugly = [1]
        i2, i3, i5 = 0, 0, 0
        while n > 1:
            u2, u3, u5 = 2 * ugly[i2], 3 * ugly[i3], 5 * ugly[i5]
            umin = min((u2, u3, u5))
            if umin == u2:
                i2 += 1
            if umin == u3:
                i3 += 1
            if umin == u5:
                i5 += 1
            ugly.append(umin)
            n -= 1
        return ugly[-1]

313 https://leetcode.com/problems/super-ugly-number/

위 코드에서 입력받아서 돌아가게끔으로만 바꾼다.

class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        ugly = [1]
        index_list = [0]*len(primes)
        while n > 1:
            umin = min([v*ugly[index_list[i]] for i,v in enumerate(primes)])
            for i,v in enumerate(primes):
                if umin == v*ugly[index_list[i]]:
                    index_list[i] += 1
            ugly.append(umin)
            n -= 1
        return ugly[-1]