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

난이도 : LV 2

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/178870?language=python3

문제해결 아이디어

• 범위가 1,000,000 까지이므로 중첩 for문은 시간 초과날것으로 예상했다
• 그래서 투포인터 방법을 활용했다.

소스코드

def solution(seq, k):
    n = len(seq)
    left = 0
    right = 0
    
    acc_num = [seq[0]]
    
    ans = []
    
    if seq[0] == k:
        ans.append([0,0])
    
    for i in range(1,n):
        acc_num.append(acc_num[-1]+seq[i])
        if acc_num[i] == k:
            ans.append([0,i])
    
    while left <= right:
        if acc_num[right] - acc_num[left] == k:
            ans.append([left+1, right])
            right += 1
            if right == n:
                break
        
        elif acc_num[right] - acc_num[left] < k:
            right += 1
            if right == n:
                break
            
        elif acc_num[right] - acc_num[left] > k:
            left += 1            
    ans.sort()
    ans.sort(key=lambda x:(x[1]-x[0]))
    
    return ans[0]
        

여담

엣지케이스를 한번에 처리 못해서 코드가 많이 지저분하게 짜졌다. 다른사람들의 풀이를 참고해서 엣지케이스까지 한번에 처리하는 풀이를 봐야겠다.