264. Ugly Number II (Heap)

이 전에 못 생긴 수 문제를 풀었더랬죠.

 

https://ggodong.tistory.com/222

263. Ugly Number

 

이 문제의 경우엔 Part 2 입니다. 최근 라스트 오브 어스 Part 2가 망했다던데.. 이 문제는 어떨까요 ?

 

팡야 !

 

---

본 문제는 2, 3, 5를 공약수로 가지는 수를 나열했을 때 N 번째 오는 숫자가 무엇인지를 알아내는 문제입니다.

 

N의 범위는 1690까지이죠.

 

이 문제 같은 경우엔 정말 많은 해법을 가지고 있습니다. 저 같은 경우엔 Heap을 사용했습니다.

 

Heap 자료구조란 우선순위를 매겨서, 항상 최우선의 우선순위를 가진 자료를 가져올 수 있는 자료구조입니다.

 

---

https://ggodong.tistory.com/88?category=793978

우선순위 큐 구현

Heap에 관련된 포스팅입니다. 참고하시면 문제를 푸는데 도움이 될 거 같네요.

---

우선 숫자 1은 무조건 못 생긴 수이기 때문에 초기에 값을 넣어넣고 뺍니다.

 

빼는 순간 ! N을 1 감소 시키고, 다시 뺀 수를 2, 3, 5를 곱해서 넣습니다.

 

그리고 다시 힙에서 하나를 뺍니다. 그리고 N을 1 감소시키고 다시 넣습니다. 이런 식으로 해서 N이 0이 되는 순간의 숫자를 뱉어내면 문제가 해결됩니다...... 면 문제가 Medium 난이도가 아니었겠죠.

 

문제는 중복된 수가 있을 수 있다는 점입니다.

 

2 * 3 = 6 이며 3 * 2 = 6 이기 때문에 6이 두 번 들어갈 수 있습니다.

 

그래서 Heap을 사용했던게, Heap의 경우엔 어차피 우선순위가 매겨져서 나오기 때문에 우선순위가 같다면, 반드시 하나의 숫자 다음에 같은 숫자가 나오기 마련입니다.

 

그렇기에 이전 숫자와 현재 숫자를 비교하여 중복된 수였는지를 비교한다면 해결될 수 있는 문제였죠.

 

밑에 코드를 봅시다.

class Solution:
    def __init__(self):
        self.tree = [0 for i in range(100000)]
        self.lastnode = 1 # 0일 때 Empty
        
    def push(self, data: int):
        self.lastnode += 1
        self.tree[self.lastnode] = data
        
        c = self.lastnode
        p = c // 2
        
        while p > 0:
            if self.tree[p] > self.tree[c]:
                temp = self.tree[p]
                self.tree[p] = self.tree[c]
                self.tree[c] = temp
                c = p
                p = c // 2
            else: break
        
        
    def pop(self):
        result = self.tree[1]
        
        self.tree[1] = self.tree[self.lastnode]
        self.lastnode -= 1

        
        p = 1
        l = 2
        r = 3
        
        while l <= self.lastnode:
            if l == self.lastnode:
                c = l
            elif self.tree[l] <= self.tree[r]:
                c = l
            elif self.tree[r] < self.tree[l] :
                c = r
            
            if self.tree[c] < self.tree[p]:
                temp = self.tree[p]
                self.tree[p] = self.tree[c]
                self.tree[c] = temp
                p = c
                l = p * 2
                r = l + 1
            else:
                break
                
        return result
        
    def nthUglyNumber(self, n: int) -> int:
        self.tree[1] = 1
        last = 0
        while 1:
            val = self.pop()
            if last != val:         
                n -= 1
                if n == 0:
                    return val
                self.push(val * 2)
                self.push(val * 3)
                self.push(val * 5)
                last = val

이렇게 힙을 이용해서 문제를 해결할 수 있었습니다 !! .....

 

????????

 

4876ms면 거의 5촌데 왜 시간 초과 안뜨죠..?

 

어찌됐건 Heap을 쓰면 너무 오래걸리네요 ㅠㅠ

 

한 번 다른 방법으로 풀어봐야겠습니다.

 

혹시... DP는 ..?

 

---

이상 264 Ugly Number II였습니다. ^_^