N개의 수로 된 수열 A[1], A[2], ..., A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i]+A[i+1]+...+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.
처음에는 이중 for문으로 문제를 풀었으나 시간초과도가 발생했다.
cnt = 0
for i in range(len(num)):
sum = 0
val = []
for j in range(i, len(num)):
sum += num[j]
#print(f'i:{i}')
if sum == M:
cnt += 1
break
print(cnt)
어떻게든 O(n)으로 풀어야하는 상황이었다.
배열 한 사이클을 돌때 끝내야 하는 상황이므로 while True, 또는 for문 한 개로 끝내야 하는데,
결국 풀지 못해 강의를 참고해서 풀었다.
lt, rt = 0, 1
sum = num[0]
cnt = 0
while True:
if sum == M:
cnt += 1
sum -= num[lt]
lt += 1
elif sum < M:
if rt < N:
sum += num[rt]
rt += 1
else:
break
else:
sum -= num[lt]
lt += 1
print(cnt)
lt, rt라는 왼쪽/오른쪽 인덱스를 두어, 각 조건에 맞게 인덱스를 이동시키는 방식이었다.
이해하면 쉽지만 접근하기가 쉽지않았다.