연속된 부분 수열의 합

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

프로그래머스

 

 

문제 개요

 

합이 k와 같은 부분수열을 찿는 알고리즘을 설계, 구현하는 것이 목표이다.

 

투 포인터 알고리즘을 써서 일정한 범위의 부분합을 구해야 한다.

 

 

 

단, 부분합을 구할 때 sum을 쓰면 시간 초과 오류가 발생한다. 

 

sum의 시간 복잡도는 O(n) 이다.

 

투 포인터 알고리즘에서 매번 sum을 사용하여 부분합을 구하면, 시간 복잡도는 최소 O(n^2)으로 늘어난다.

 

주어지는 데이터의 크기가 최대 1,000,000 인 경우에 위의 알고리즘을 적용하면, 시간 초과가 발생한다.

 

 

따라서 매번 sum으로 부분합을 구하는 대신, 탐색 범위를 변경함과 동시에 부분합에도 변화를 줘야 한다.

 

 

알고리즘 및 풀이

1. 변수 정의

    ans = []              # 답안 저장
    l, r = 0, 0           # 부분 수열의 좌, 우 경계
    n = len(sequence)     
    tmp = sequence[0]     # 임시 부분합

 

 

부분합을 초기화 함으로써, 탐색 과정에서 sum 연산을 반복할 필요를 없앨 수 있다.

 

 

 

2. 탐색

 

1) 부분합이 목표값보다 작은 경우

    while l <= r and r <= n :
        # 1) 부분합 < 목표값인 경우
        if tmp < k:
            r += 1        # 부분 수열 범위를 늘리기
            if r == n:      # 부분 수열이 끝에 도달하면
                break       # 탐색 종료
            else:           
                tmp += sequence[r]  # 부분수열에 새로 들어온 부분의 값 sequence[r] 만큼 부분합에 더해주기

 

부분수열을 오른쪽으로 1칸 늘려준다.

 

만약 원래 수열의 범위를 넘어간다면, 그 자리에서 탐색을 종료한다.

 

아니라면,  sequence[r] 만큼 부분합에 더해준다.

 

 

2) 부분합이 목표값보다 크거나, 같은 경우

        # 2) 부분합 >= 목표값인 경우
        else:
            if tmp == k:    # 부분합 == 목표값
                if len(ans) == 0 or (len(ans) != 0 and (ans[1] - ans[0]) > (r - l)):
                    # 답을 못찾았거나, 이전에 찾은 답보다 길이가 짧다면
                    ans = [l, r]
            
            tmp -= sequence[l]  # 부분합에서, 부분수열의 맨 왼쪽 숫자만큼 빼기
            l += 1  # # 부분수열 범위를 왼쪽에서 한칸 줄이기

 

 

부분합이 목표값과 같아도, 새로 구한 부분 수열의  범위가 이전 답안보다 작은 경우에만 답안을 갱신해야 한다.

 

이는 문제에서 "합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다." 라고 명시했기 때문이다.

 

이전과 비교할 답안이 없다면, 그대로 답안을 갱신해준다.

 

 

다음으로, 부분수열에서 맨 왼쪽 값만큼 빼줘야 한다.

 

부분 수열에서 맨 왼쪽값을 빼줘야, 부분합을 줄이고, 탐색을 진행할 수 있기 때문이다.

 

 

 

전체 코드

"""
    - 문제 위치: https://school.programmers.co.kr/learn/courses/30/lessons/178870
    - 참고 풀이: https://velog.io/@sugyeonghh/프로그래머스-연속된-부분-수열의-합Python 
"""


def solution(sequence, k):
    ans = []
    l, r = 0, 0
    n = len(sequence)
    tmp = sequence[0]
    
    while l <= r and r <= n :
        # 1) 부분합 < 목표값인 경우
        if tmp < k:
            r += 1        # 우측 경계를 오른쪽으로 한칸 이동
            if r == n:      # 부분 수열이 끝에 도달하면
                break       # 탐색 종료
            else:           
                tmp += sequence[r]  # sequence[r] 만큼 부분합에 더해주기
        # 2) 부분합 >= 목표값인 경우
        else:
            if tmp == k:    # 부분합 == 목표값
                if len(ans) == 0 or (len(ans) != 0 and (ans[1] - ans[0]) > (r - l)):
                    # 답을 못찾았거나, 이전에 찾은 답보다 길이가 짧다면
                    ans = [l, r]
            
            tmp -= sequence[l]  # 부분합에서, 부분수열의 맨 왼쪽 숫자만큼 빼기
            l += 1  # # 부분수열 범위를 왼쪽에서 한칸 줄이기
            
    return ans