sum 시간복잡도

for문과 sum을 이용하여 문제를 풀었다가 답은 맞췄는데 시간 초과로 인하여 실패한 경우가 발생했다..

 

처음에는 반복문 혹은 반복문 안에 있는 조건문의 문제인줄 알았는데 구글링해보니 sum()이 시간복잡도가 O(n)이라 반복문을 돌릴때마다 시간을 잡아먹은 것이었고 결국 sum을 미리 정의하지 않고 반복문에서 매순서때마다 일일이 적용한 것이 문제였다..

 

앞으로 코테 문제 풀때는 반복문에서 sum, max, min과 같은 리스트 관련 수학 메소드을 사용하는 것은 자제하고 해결한 문제처럼 사전에 처리한 변수를 정의하여 사용해야 할듯하다. 

https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

# 문제 해결 전 코드
from collections import deque
def solution(queue1, queue2):
    answer = 0
    queue1, queue2 = deque(queue1), deque(queue2)
    standard = (sum(queue1) + sum(queue2)) / 2
    if standard < max(queue1) or standard < max(queue2):
        return -1
        
    for i in range(len(queue1) * 3):
        if sum(queue1) > sum(queue2):
            queue2.append(queue1.popleft())
            answer += 1
            
        elif sum(queue1) < sum(queue2):
            queue1.append(queue2.popleft())
            answer += 1
            
        else:
            return answer
        
    return -1
    
# 문제 해결 후 코드
from collections import deque
def solution(queue1, queue2):
    answer = 0
    queue1, queue2 = deque(queue1), deque(queue2)
    sum1, sum2 = sum(queue1), sum(queue2)

    for i in range(len(queue1) * 3):
        if sum1 > sum2:
            sum1 -= queue1[0]
            sum2 += queue1[0]
            queue2.append(queue1.popleft())
            answer += 1

        elif sum1 < sum2:
            sum1 += queue2[0]
            sum2 -= queue2[0]
            queue1.append(queue2.popleft())
            answer += 1

        else:
            return answer

    return -1