프로그래머스_연속된 부분 수열의 합(python)

※ 접근

 sequence의 길이가 최대 백만이었기에 중첩 포문을 돌면 안되겠다는 생각이 제일 먼저 떠올랐다.  구간 합을 구하고 그 구간이 계속 변해가야하기에 left,right 투 포인터를 사용하기로 했다. 

 

※ 풀이

 1. 첫 시작과 나중을 구분했다. 그 이유는 처음에는 k를 같든 작든 크든 right가 오른쪽으로 이동해줘야 하기 때문이다.

(right는 left보다 같거나 큰 idx에 위치해야 하기 때문이다. )

2. temp == k라면 구간의 길이를 key로 하고 left, right를 사전형에 추가시켜준다. left와 right를 오른쪽으로 한 칸씩 이동시켜준다.

3. temp > k라면 left를 줄여준다.

4. temp < k라면 right를 한 칸 오른쪽으로 이동시켜준다. 

5. 마지막에 가장 작은 key를 찾아 첫 인덱스 별로 정렬 시켜주고 0번 인덱스를 answer에 넣어주면된다.

from collections import defaultdict

def solution(sequence, k):
    s = defaultdict(list)
    temp = 0
    left, right = 0, 0
    temp, i = 0, 0
    while right < len(sequence) and left < len(sequence): 
        if i == 0:
            temp = sequence[0]
            if temp == k:
                s[right+1-left].append([left,right])
            right += 1 # 처음에는 일단 right가 넘어가는게 맞음
            if not right < len(sequence):
                break
            temp += sequence[right]
            i += 1
        else:
            if temp == k:
                s[right+1-left].append([left,right])
                temp -= sequence[left]
                left += 1
                right += 1
                if not right < len(sequence):
                    break
                temp += sequence[right]
            elif temp > k:
                temp -= sequence[left]
                left += 1
            else:
                right += 1
                if not right < len(sequence):
                    break
                temp += sequence[right]
    
    min_len = min(s.keys())
    min_list = s[min_len]
    min_list = sorted(min_list, key=lambda x:x[0])
    answer = min_list[0]
    return answer

※ 회고

 화이팅!!!