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

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

프로그래머스

 

lv2

 

문제 이해

붙어 있는 수들의 합으로 k를 만들어야 한다.

답이 여러개인 경우 길이가 가장 짧은 수열을 찾아야 한다.

길이가 가장 짧은 수열이 여러개인 경우 앞쪽에 나오는 수열을 찾는다.

 

 

접근법

투포인터 알고리즘을 사용하여 합이 k 인 부분 수열을 찾는다. 

 

right가 오른쪽 끝까지 갈때 까지 반복문을 돌린다.

1. 합이 k와 같은 경우 

- 해당 부분의 수열의 길이를 계산하고 가장 짧은 길이를 업데이트한다.

- left부분을 오른쪽으로 이동해 새로운 부분 순열 검사를 시작한다.

2. 합이 k와 작거나 큰경우

- k보다 작은 경우 right부분을 오른쪽으로 이동하여 새로운 부분 수열을 확장한다. (현재 부분수열로 k보다 작으니 더 합하기 위해)

- k보다 큰 경우 left 부분을 오른쪽으로 이동하여 부분수열의 첫 번째 요소를 제거한다. (이전 부분수열은 k보다 작고 현재 부분 수열은 k보다 크니 숫자가 작은 왼쪽 요소를 제거하 k와 맞춤)

 

 

코드

def solution(sequence, k):
    left, right = 0, 0 # 투 포인터
    curr_sum = sequence[0]
    shortest_len = float('inf')
    shortest_subseq = []

    while right < len(sequence):
        print(left, right)
        if curr_sum == k:
            curr_len = right - left + 1
            # 길이가 가장 짧은 수열 업데이트 
            if curr_len < shortest_len:
                shortest_len = curr_len
                shortest_subseq = [left, right]

            curr_sum -= sequence[left]
            left += 1
            
        # k보다 작은 경우 right 를 오른쪽으로 이동시켜 부분배열에 추가하도록
        elif curr_sum < k:
            right += 1
            if right < len(sequence):
                curr_sum += sequence[right]
                
        # k보다 큰경우 left를 오른쪽으로 이동시키며 왼쪽 요소를 삭제
        else:
            curr_sum -= sequence[left]
            left += 1
    return shortest_subseq

---

 

투 포인터 알고리즘?

- 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

 

대표 예제

1. 시작 점과 끝 점이 첫 번째 원소의 인덱스를 가르키도록 한다.

2. 현재 부분 합이 result와 같다면 카운트한다.

3. 현재 부분 합이 result보다 작다면 끝 점을 1 증가시킨다

4. 현재 부분 합이 result보다 크다면 시작 점을 1 증가시킨다.

5. 2~4를 반복한다.

 

시간 복잡도 

- O(N)