• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

for 문 사용 시 조건문으로 break할 때의 시간 복잡도

20.05.27 12:01 작성 조회수 197

0

챕터 3-5의 수열의 합을 먼저 풀어봤을 때 제가 작성했던 코드입니다. for 문을 두 번 사용해서 그런지 채점시 3번부터 time out이 떴습니다. 두 번 째 for 문에서 조건을 충족하는 경우 break를 써서 시간 복잡도를 줄여줬다고 생각했는데 왜 시간 초과가 뜨는 지 모르겠습니다. 좋은 강의 항상 고맙습니다.

cnt=0
for i in range(n):
    if a[i] > m:
        continue
    elif a[i] == m:
        cnt += 1
    else:
        for j in range(i+1, n+1):
            if sum(a[i:j]) > m:
                break
            if sum(a[i:j]) == m:
                cnt+=1
                break

답변 1

답변을 작성해보세요.

0

이 문제는 시간복잡도가 O(n)으로 풀어야 100점이 나오도록 데이터를 만들었습니다. 

2중 for문을 돌려서는 100점이 나오지 않도록 했습니다.