[프로그래머스] [python] 연속된 부분 수열의 합 : 투 포인터 알고리즘

기존 코드

코드 실행은 성공했지만 시간 초과로 실패한 코드이다. 나름 python 리스트 filter와 리스트 comprehension을 이용하여 조건을 잘 필터링 했다고 생각했지만, 이중 반복문을 사용하여 시간 초과가 걸렸다.

def solution(sequence, k):
    answer = []
    n = len(sequence)
    smallest = n-1
    for i in range(n):
        sum = 0
        j = i
        while sum<=k and j<n:
            sum += sequence[j]
            if sum == k:
                answer.append([i,j,j-i])
                if (j-i) <= smallest:
                    smallest = j-i
                break
            j += 1
    if len(answer) == 1:
        return answer[0][0:-1]
    else:
        filtered = [x for x in answer if x[2]==smallest]
        min_answer = min(filtered, key=lambda x: x[0])
        return min_answer[0:-1]

투 포인터(Two pointer) 알고리즘

투 포인터는 데이터에 순차적으로 접근해야 할 때 두 개의 점 위치를 조절하여 조건에 부합하는지 판단하는 알고리즘이다.

공통 부분을 제외하고 포인터로 이동하는 원소의 처리만 하면 되므로 유용하게 쓰일 수 있다.

특정한 합을 가지는 부분 연속 수열의 개수를 구하는 알고리즘

n, target = map(int,input().split())
arr = list(map(int,input().split()))

cnt, sum = 0, 0
high, low = 0, 0
while(1):
    if sum > target:        # 합이 타겟보다 크면
        sum -= arr[low]     # sum에서 뺴고
        low += 1            # low 의 index를 1증가
    elif high == n: break
    else:
        sum+=arr[high]      # 합이 타겟보다 작거나 같다면
        high+=1             # sum에 더하고 high의 인덱스를 1증가
    if sum==target:
        cnt+=1
print(cnt)

정답 코드

def solution(sequence, k):
    answer = []
    n = len(sequence)
    
    sum = 0
    high, low = 0,0
    while(True):
        if sum > k:
            sum -= sequence[low]
            low += 1
        elif high == n: break
        else:
            sum += sequence[high]
            high += 1
        if sum == k:
            answer.append([low, high-1])

    answer.sort(key = lambda x: (x[1]-x[0],x[0]))
    return answer[0]

투 포인터 알고리즘을 이용하여 부분 수열을 모두 찾는다.

가장 길이가 짧고 인덱스가 앞인 배열을 찾는 로직도 sort를 이용해 개선하여 작성하였다.

sort 조건

• 기준 1 ) 길이 짧은 순 -> x[1] - x[0]
• 기준 2 ) 인덱스 작은 순 -> x[0]

 

참고한 글

https://velog.io/@nana-moon/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0Sliding-window-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0Two-pointer

[알고리즘] 슬라이딩 윈도우(Sliding window), 투 포인터(Two pointer)