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

문제 

https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

 

 

 

문제 접근 방식

비내림차순으로 정렬된 리스트에서 연속된 부분의 합이 k를 만족하는 리스트 중 길이가 가장 짧고 앞에 있는 부분을 구하는 문제이다. 연속된 부분합을 짧은 시간복잡도로 구할 수 있는 투포인터을 활용하여 문제를 풀려고 했다. 또한, 해당 투포인터로 구한 부분 수열의 합이 k 와 같다면, 해당 리스트의 [길이, 시작 인덱스, 마지막 인덱스] 값을 candidates 리스트에 저장해서 마지막에 [길이 > 시작 인덱스] 순서로 정렬이 되도록 문제를 풀었다.

 

 

시간 복잡도

투포인터의 경우 리스트를 한번 순회하는데 O(N)이 걸리며, N의 최댓값이 1e6이기 때문에 시간 내에 동작함을 알 수 있다.

 

 

코드

def solution(sequence, k):
    n=len(sequence)
    start,end=0,0
    total=0
    candidates=[]
    
    #부분 수열의 끝점 end로 리스트를 순회한다.
    for end in range(n):
    	
        # 해당 리스트의 끝 숫자자를 부분수열 합에 더해준다.
        total+=sequence[end]

        if total < k: # 부분수열의 합이 k 보다 작다면, end 를 옮겨 숫자가 늘어나도록 한다. 
            continue
        elif total==k: # 부분수열의 합이 k 와 같다면 candidates에 추가하고, end를 오른쪽으로 옮긴다.
            candidates.append([end-start+1,start,end])
            continue
        
        # 합이 k 보다 큰 경우로, 이때는 왼쪽의 start를 오른쪽으로 옮겨서 합을 감소시킨다.
        while start<=end: 
            if total < k: # 합이 k 보다 작게 되면 멈춘다.
                break
            if total==k: # k와 같다면 candidates에 넣어준다.
                candidates.append([end-start+1,start,end])
                break
            total-=sequence[start] # start 위치의 숫자를 감소시켜 부분합을 감소시킨다.
            start+=1
        
    # [길이 > 시작 위치] 순으로 정렬한다.    
    sort_answer=sorted(candidates,key=lambda x:(x[0],x[1]))
   
    return [sort_answer[0][1],sort_answer[0][2]]

 

 

회고

연속된 부분 합을 구하는 투포인터 방식을 활용하여 문제를 풀었는데, 첫 구현을 해보는거다 보니 풀면서 버벅였다. 깔끔하게 작성된 코드를 보고 정리가 필요할 것 같다.