[코딩 테스트] 3일차.

수들의 합

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라는 왼쪽/오른쪽 인덱스를 두어, 각 조건에 맞게 인덱스를 이동시키는 방식이었다.
이해하면 쉽지만 접근하기가 쉽지않았다.