강의로 돌아가기
박기완

효율성 테스트를 통과하고 싶습니다.

최대한 heap을 이용하고, heap의 길이를 줄여도 보았는데 계속 효율성 테스트에서 시간 초과가 일어납니다.
어느 부분을 개선하면 좋을지 조언 부탁드립니다.
감사합니다!

작성중인 코드―solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Heap():
    def __init__(self, lst):
        self.lst = lst
        for i in range(len(lst) // 2, 0, -1):
            self.go_down(i -1)

    def length(self):
        return len(self.lst)

    def root(self):
        return self.lst[0]

    def go_up(self, index):
        if index == 0:
            return 0
        parent = (index - 1) // 2

        if self.lst[parent] > self.lst[index]:
            self.lst[parent], self.lst[index] = self.lst[index], self.lst[parent]

            return self.go_up(parent)
        else:
            return index

    def go_down(self, index):
        length = len(self.lst)
        left = index * 2 + 1
        right = (index + 1) * 2

        if left < length and self.lst[left] < self.lst[index]:
            smaller = left
        else:
            smaller = index

        if right < length and self.lst[right] < self.lst[smaller]:
            smaller = right

        if smaller != index:
            self.lst[index], self.lst[smaller] = self.lst[smaller], self.lst[index]
            self.go_down(smaller)

    def insert(self, data):
        self.lst.append(data);
        return self.go_up(len(self.lst) - 1)

    def delete(self):
        if len(self.lst) == 1:
            return self.lst.pop(0)

        root = self.lst.pop(0)
        newRoot = self.lst.pop(-1)
        self.lst.insert(0, newRoot)
        self.go_down(0)
        return root

def mix_food(a, b):
    return a + b * 2

def solution(scoville, K):
    count = 0
    under_K = [x for x in scoville if x < K]
    over_exist = len(scoville) != len(under_K)
    heap_scoville = Heap(under_K)

    if len(under_K) < 2:
        return len(under_K)

    for i in range(len(under_K)):
        if heap_scoville.length() == 1:
            if over_exist:
                return count + 1
            return -1

        value1 = heap_scoville.delete()
        value2 = heap_scoville.delete()
        mixed = mix_food(value1, value2)
        heap_scoville.insert(mixed)
        count += 1

        if heap_scoville.root() >= K:
            return count
    return -1
0 개의 답변
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.