[프로그래머스] LV.2 연속된 부분 수열의 합

프로그래머스 LV.2 연속된 부분 수열의 합

문제

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 k입니다.
• 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
• 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

제한사항

• 5 ≤ sequence의 길이 ≤ 1,000,000
  • 1 ≤ sequence의 원소 ≤ 1,000
  • sequence는 비내림차순으로 정렬되어 있습니다.
• 5 ≤ k ≤ 1,000,000,000
  • k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.

문제 풀이

1. 내 풀이
   문제를 풀 당시에는 투 포인터 라는 개념이 생각나지 않았다.
   그래서 그저 문제에서 요구한 대로 반복문을 통해 숫자를 하나씩 큐에 넣어주고, 부분합을 구했다.

   for문 구조는 다음과 같다.

   • i번째 수 이전까지의 부분합(sum)이 k보다 커지면, 큐에서 왼쪽부터 하나씩 빼면서 부분합이 k보다 작거나 같을때 까지 반복한다. 이때 start는 1씩 증가시킨다.

   • 그리고 while문이 끝난 후, 만약 부분합이 k와 같아지면, start와end를 기록한다. 이때 그 간격이 짧은 것을 찾아야 하므로 end - start < result 조건을 통해 짧은 간격일때만 기록한다.

     • 등호를 붙이지 않은 이유는 "길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다." 라는 조건 때문이다.

   • i번째 수를 큐와 부분합에 추가해주고, end를 i로 갱신.

from collections import deque


def solution(sequence, k):
    answer = []
    sequence += [0]

    q = deque()
    sum = 0
    start, end = 0, 0
    result = len(sequence)
    for i in range(len(sequence)):
        while sum > k:
            temp = q.popleft()
            sum -= temp
            start += 1
        if sum == k and end - start < result:
            answer = [start, end]
            result = end - start

        q.append(sequence[i])
        sum += sequence[i]
        end = i

    return answer

2. 투 포인터 정석 풀이
   우선 부분합을 기록할 max_sum과 끝 포인터인 end를 선언해준다.

   이후 for문을 돌리는데, 이때 시작 포인터인 start를 사용.

   로직은 간단하다. 부분합이 k보다 크거나 같을때 까지 end를 1씩 증가시키며 더해준다.

   이후 부분합이 k와 같은지 비교하고, 만약 같다면 기록을 해준다.

   그리고 마지막으로 현재 부분합은 k보다 크거나 같으므로, start 위치의 값을 빼주고 다음 반복문을 진행한다.

   즉, 정리하면 다음과 같다.

   1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다
   2. 현재 부분 합이 k와 같다면, 기록한다
   3. 현재 부분 합이 k보다 작다면, end를 1 증가시킨다
   4. 현재 부분 합이 k보다 크거나 같다면, start를 1 증가시킨다
   5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다

def solution(sequence, k):
    n = len(sequence)

    max_sum = 0
    end = 0
    interval = n

    for start in range(n):
        while max_sum < k and end < n:
            max_sum += sequence[end]
            end += 1
        if max_sum == k and end-1-start < interval:
            res = [start, end-1]
            interval = end-1-start
        max_sum -= sequence[start]

    return res