강의로 돌아가기
hy

파이썬) 효율성 테스트에서 시간초과가 되네요...

def solution(scoville, K):
    num = 0

    while(1):
        if min(scoville)>=K:
            return num
        elif len(scoville) == 1:
            return -1

        t1 = min(scoville)
        scoville.remove(t1)
        t2 = min(scoville)
        scoville.remove(t2)
        scoville.append(t1 + 2*t2)
        num += 1

처음에는 while 문 안에 sort()를 넣어서, scoville[0]과 [1]을 pop 하는 식으로 했는데,
그렇게 했더니 시간초과가 뜨더라고요.
sort() 때문인가 싶어서 정렬을 아예 안하고 min()함수만 사용하는 식으로 했는데 그래도 시간초과가 뜨네요 ㅠ
어떤게 효율이 문제인 걸까요? 혹시 remove가 그렇게 효율이 안좋은 함수인지요? ㅠㅠ

참고로 처음 한 번만 sort()하고, 정렬된 배열 사이에 함숫값을 순서에 맞춰 끼워넣는 함수를 하나 만드는 식으로 해서 while문 안에도 넣어봤는데 그것도 시간초과입니다 ㅠㅠ

1 개의 답변
Demi

Python list의 remove는 time complexity가 O(n) 입니다.
문제 카테고리가 힙인걸 참고해, 다른 적절한 자료 구조를 선택해보심이 어떨까요?

  • hy
    좋은 답변 감사합니다. hy 2018.09.28 21:48
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.