[Programmers] 연속된 부분 수열의 합 (투 포인터 Lv.2) - Python

1. 문제

---

링크텍스트

2. 풀이

---

코드

def solution(sequence, k):
    prefix_sum = [0] * (len(sequence) + 1)
    for i in range(1, len(sequence) + 1):
        prefix_sum[i] = prefix_sum[i - 1] + sequence[i - 1]

    answer = [0, len(sequence) - 1]  # 전체 sequence로 answer 초기화

    s = 0
    e = 1

    while e <= len(sequence):
        current_sum = prefix_sum[e] - prefix_sum[s]
        if current_sum == k:
            if e - 1 - s < answer[1] - answer[0]:
                answer = [s, e - 1]
            s += 1
        elif current_sum < k:
            e += 1
        else:
            s += 1

    return answer

입력 및 출력

sequence = [1, 2, 3, 4, 5]	
k = 7		

>> [2, 3]

3. 로직

---

1. prefix_sum 리스트를 초기화한다. 이 리스트는 인덱스 i까지의 부분 수열의 합을 저장하는 접두사 합계(prefix sum)를 나타낸다. 초기 값은 모두 0으로 설정한다.

2. sequence의 각 요소를 순회하면서 접두사 합계를 계산하여 prefix_sum 리스트에 저장한다. 인덱스 i의 접두사 합계는 prefix_sum[i] = prefix_sum[i-1] + sequence[i-1]로 계산된다.

3. answer 리스트를 초기화한다. 이 리스트는 가장 가까운 합을 가진 부분 수열의 시작 인덱스와 끝 인덱스를 저장한다. 초기 값으로는 전체 수열의 시작과 끝을 나타내는 [0, len(sequence)-1]을 설정한다.

4. 변수 s와 e를 초기화한다. s는 부분 수열의 시작 인덱스를 나타내며 0으로, e는 부분 수열의 끝 다음 인덱스를 나타내며 1로 설정한다.

5. while 루프를 통해 가능한 모든 연속된 부분 수열을 검사한다. 루프는 e가 수열의 길이를 넘지 않을 때까지 실행된다.

6. 현재 부분 수열의 합인 current_sum을 계산한다. 이는 prefix_sum[e] - prefix_sum[s]로 계산된다.

7. current_sum과 k를 비교하여 세 가지 경우를 고려한다.

   • current_sum이 k와 동일한 경우: 현재 부분 수열의 길이가 기존 answer 부분 수열의 길이보다 작으면 answer를 갱신한다.
   • current_sum이 k보다 작은 경우: 부분 수열의 합을 더 크게 만들기 위해 e를 증가시킨다.
   • current_sum이 k보다 큰 경우: 부분 수열의 합을 줄이기 위해 s를 증가시킨다.

8. answer를 반환한다. 이는 합이 k와 가장 가까운 부분 수열의 시작 인덱스와 끝 인덱스를 담고 있다.

4. 그림

---