강의로 돌아가기
임동진

효율성 기준이 다소 과한 것이 아닌지 의심이 듭니다.

저는 heapq 라이브러리를 사용하지않고, 직접 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
class BinHeap:
    def __init__(self):
        self.data = []
        self.length = 0
        self.real_length = 0

    def insert(self, value):
        if self.real_length != 0 and len(self.data) > self.length:
            self.data[self.length] = value
        else:
            self.data.append(value)
            self.real_length += 1
        self.length += 1
        idx = self.length - 1
        while idx > 0:
            p = (idx) // 2
            if self.data[idx] < self.data[p]:
                self.data[idx], self.data[p], idx = self.data[p], \
                                                    self.data[idx], p
            else:
                break

    def remove(self):
        assert self.length != 0
        idx = self.length - 1

        poped_value = self.data[0]
        last_value = self.data[idx]
        self.length -= 1
        self.data[0] = last_value
        idx = 0
        while idx < self.length:
            c = (idx) * 2 + 1
            if c < self.length - 1 and self.data[c] > self.data[c + 1]:
                c = c + 1
            if c >= self.length:
                break
            if c < self.length and self.data[idx] > self.data[c]:
                self.data[idx], self.data[c], idx = self.data[c], \
                                                    self.data[idx], c
                continue
            else:
                break

        self.data[self.length] = None
        return poped_value

def solution(scoville, K):
    answer = 0
    heap = BinHeap()
    for s in scoville:
        heap.insert(s)
    while heap.data[0] < K and heap.length != 0:
        if heap.length == 1:
            return -1
        first = heap.remove()
        second = heap.remove()
        heap.insert(first + (2 * second))
        answer += 1
    if heap.data[0] < K or heap.length == 0:
        return -1
    return answer
0 개의 답변
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.