[프로그래머스] 연속된 부분 수열의 합 (python)

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

 

문제

 

풀이

- 슬라이딩 윈도우

슬라이딩 윈도우 알고리즘은 배열을 일정한 크기의 "창"으로 유지하면서 창을 왼쪽에서 오른쪽으로 이동시켜 원하는 조건을 만족하는 부분 배열을 찾는 방식

 

단계별 풀이

1. 변수 초기화:
   • left 포인터: 슬라이딩 윈도우의 왼쪽 끝을 가리키는 포인터로 초기값을 0으로 설정합니다.
   • right 포인터: 슬라이딩 윈도우의 오른쪽 끝을 가리키는 포인터로 초기값을 0으로 설정합니다.
   • current_sum: 현재 슬라이딩 윈도우 안의 원소들의 합을 저장하는 변수로 초기값을 0으로 설정합니다.
   • best_range: 합이 k인 부분 수열 중 가장 짧은 수열의 시작과 끝 인덱스를 저장하는 변수로, 초기값을 [0, inf]로 설정합니다. 여기서 inf는 무한대를 나타내며, 비교를 위해 사용합니다.
2. 윈도우 확장 및 축소:
   • right 포인터를 순차적으로 증가시키면서 윈도우에 원소를 추가합니다. 이때 current_sum에 sequence[right]를 더합니다.
   • current_sum이 k와 같아질 때까지 right 포인터를 이동시키면서 윈도우를 확장합니다.
   • 만약 current_sum이 k와 같다면, 윈도우의 길이를 계산합니다. 길이가 기존의 최적값(best_range)보다 짧으면 best_range를 갱신합니다. 길이가 같다면, left가 더 작은 경우로 갱신합니다.
   • current_sum이 k보다 크거나 같다면, left 포인터를 오른쪽으로 이동시켜 윈도우를 축소합니다. 이때 sequence[left]를 current_sum에서 빼줍니다.
3. 윈도우 이동:
   • left 포인터가 right 포인터를 초과하지 않는 범위에서 윈도우를 축소하고, current_sum이 k보다 작아질 때까지 윈도우를 계속해서 축소합니다.
4. 결과 반환:
   • 모든 포인터 이동이 끝나면 best_range에 저장된 값이 원하는 부분 수열의 시작과 끝 인덱스를 담고 있을 것입니다.
   • [best_range[0], best_range[1]]를 반환합니다.

def solution(sequence, k):
    n = len(sequence)
    left = 0
    current_sum = 0
    best_range = None

    for right in range(n):
        current_sum += sequence[right]
        
        # current_sum이 k 넘칠
        while current_sum > k and left <= right: 
            current_sum -= sequence[left]
            left += 1
        
        # current_sum이 k와 같을 때
        # 부분 수열의 길이를 확인
        if current_sum == k:
            # 아직 best range가 없거나, 새로운 게 길이가 더 을 때
            if best_range is None or (right - left < best_range[1] - best_range[0]):
                best_range = [left, right]
            # 길이가 똑같으면 시작 인덱스가 작은 수열로  
            elif right - left == best_range[1] - best_range[0] and left < best_range[0]:
                best_range = [left, right]
                                 
       # 넘치지도 같지도 않고, 여전히 작으면 right를 한 칸 더 이동


    return best_range

 

def solution(sequence, k):
    left, right = 0, 0
    current_sum = sequence[0]
    best_range = [0, float('inf')]

    while right < len(sequence):
        if current_sum == k:
            # 현재 윈도우가 k와 같은 경우 길이 비교
            if (right - left) < (best_range[1] - best_range[0]):
                best_range = [left, right]
            elif (right - left) == (best_range[1] - best_range[0]) and left < best_range[0]:
                best_range = [left, right]

        if current_sum >= k:
            current_sum -= sequence[left]
            left += 1
        else:
            right += 1
            if right < len(sequence):
                current_sum += sequence[right]

    return best_range