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

링크

문제 설명

def solution(sequence: List[int], k: int) -> List[int]:
    ...

주어진 비내림차순 배열 sequence에 대해 합이 k인 부분 배열 중 가장 길이가 짧은 구간을 구해 반환한다.

• 비내림차순 : 인접한 두 수가 같을 수도 있는 오름차순

sequence	k	result
[1, 2, 3, 4, 5]	7	[2, 3]
[1, 1, 1, 2, 3, 4, 5]	5	[6, 6]
[2, 2, 2, 2, 2]	6	[0, 2]

제한사항

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

풀이

부분 배열의 시작과 끝을 나타내는 start와 end를 만들어 구간의 합을 구하고 k와 비교하는 방식으로 문제를 해결했다. 구간의 합이 k보다 작을 경우 end를 오른쪽으로 옮기고, 구간의 합이 k보다 클 경우 start를 오른쪽으로 옮긴다. 이렇게 구한 구간들을 비교해 가장 길이가 짧은 것을 정답으로 반환한다.

제출코드

def solution(sequence: List[int], k: int) -> List[int]:
        answer = []
    start, end = 0, 0
    sum_val = sequence[0]
    min_len = len(sequence)
    while end < len(sequence):
        if sum_val == k:
            if end - start < min_len:
                answer = [start, end]
                min_len = end - start
            sum_val -= sequence[start]
            start += 1
        elif sum_val < k:
            end += 1
            if end < len(sequence):
                sum_val += sequence[end]
        else:
            sum_val -= sequence[start]
            start += 1
    return answer