-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
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
답변을 작성해보세요.
0
김태원
지식공유자2020.05.27
이 문제는 시간복잡도가 O(n)으로 풀어야 100점이 나오도록 데이터를 만들었습니다.
2중 for문을 돌려서는 100점이 나오지 않도록 했습니다.
답변 1