[프로그래머스] 178870 파이썬 - 연속된 부분 수열의 합 (투포인터 알고리즘)

 

문제 이름과 제한 사항 (sequence의 길이 <= 1000,000)을 보고 바로 투포인터 알고리즘이 생각났다.

 

투포인터 알고리즘?

- 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

- 특정한 합을 가지는 부분 연속 수열 찾기와 같은 문제 & 정렬되어 있는 배열 문제에 대표적으로 사용됨

- 시작점은 끝점보다 작거나 같다는 조건을 항상 만족해야 한다.

- 시간복잡도는 O(N)    

    - 포인터가 N번 증가해야 알고리즘이 끝나므로 하나의 포인터의 시간복잡도는 O(N)

      2 * O(N) = O(N) 이므로 합쳐도 시간복잡도는 O(N)

 

풀이

1. start, end 각각 0으로 설정 & 두 포인터 사이의 값의 합 sumNum = sequence[start]으로 초기화

    1-1. sumNum이 k보다 크거나 같으면 start += 1

    1-2. sumNum이 k보다 작으면 end += 1

    1-3. sumNum이 k와 같으면 answer에 [start,end]를 append

2. 위의 과정을 반복하며 start나 end 값이 len(sequence)와 크거나 같아지면 while문을 탈출.

3. answer 리스트에는 연속된 부분 수열의 합이 k인 인덱스 짝들이 저장되게 된다.

4. 길이가 짧은 수열 + 시작 인덱스가 작은 수열을 찾아야 하므로

answer에 각 인덱스 짝들에 길이(answer[i][1]-answer[i][0])를 append 해주었고, 

answer.sort(key = lambda x: (x[2],x[0],x[1]))라는 lambda 함수를 사용하여 조건에 맞는 수열을 찾아내었다.

 

코드

def solution(sequence, k):
    answer = []
    
    n = len(sequence)
    start = 0
    end = 0
    sumNum = sequence[start]
    
    while True:
        if sumNum >= k:
            if sumNum == k:
                answer.append([start,end])
            sumNum -= sequence[start]
            start+=1
            if start >= n:
                break  
        elif sumNum < k:
            end += 1
            if end >= n:
                break
            sumNum += sequence[end]
    
    for i in range(len(answer)):
        answer[i].append(answer[i][1]-answer[i][0])
    answer.sort(key = lambda x: (x[2],x[0],x[1]))
    
    return answer[0][0:2]

 

 

프로그래머스