99클럽 - 연속된 부분 수열의 합

프로그래머스

아이디어

가장 처음 생각해 볼 수 있는 방법은 무빙 윈도우로 다음과 같다.

• head를 0, tail을 1로 초기화한다.
• head ~ tail의 합이 k보다 작으면 tail을 1 증가 시킨다.
• head ~ tail의 합이 k보다 크면 head를 1 증가 시킨다.
• head ~ tail의 합이 k와 같으면 이 둘을 저장하고 head를 1 증가 시킨다.
• head와 tail이 같으면 tail을 1 증가 시킨다.
• 저장된 head와 tail 쌍중 tail - head의 값이 작은 순으로 정렬한다.
• 정렬된 쌍들 중 tail - head의 값이 0번째와 같은 값들을 남긴다.
• 남은 쌍들중 head의 값이 가장 작은 쌍을 찾는다.

이대로도 문제는 풀리지만 제약조건이 무지막지한데

• 배열의 길이가 최대 1,000,000 이다.
• k의 값이 최대 1,000,000,000 이다.

당연히 테스트 케이스를 통과할 수 있을 리 없다.

풀이

def solution(sequence, k):
    tot = 0
    
    for idx in range(len(sequence)-1, -1, -1):
        tot += sequence[idx]
        
        if tot > k:
            tot -= sequence.pop()
        
        if tot == k:
            while sequence[idx - 1] == sequence[-1] and idx > 0:
                idx -= 1
                sequence.pop()
            return [idx, len(sequence) - 1]

그래서 무빙 윈도우를 변형해 탐색을 진행하고, 이 과정에서 예외처리를 통해 불필요한 연산을 없애주려는 노력이 필요하다.