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

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

프로그래머스

 

접근법1

이중 반복문을 통해 조건을 만족하는 부분 수열을 구하는 방식으로 진행했지만, 이중 반복문 사용으로 시간초과가 발생했습니다.

 

문제풀이

def solution(sequence, k):
    answer = [0,1000000]
    
    len_seq= len(sequence)

    for i in range(len_seq) :
        sum_i = 0
        for j in range(i,len_seq) :
            if sum_i+sequence[j] == k :
                if answer[1]-answer[0] > j-i :
                    answer = [i,j]
                break
            elif sum_i+sequence[j] > k :
                break
            sum_i+=sequence[j]

    return answer

 

접근법2

이중 반복문을 사용하면 사용시 시간초과 발생하기 때문에 투포인터 알고리즘을 사용하여 해결했습니다.

start, end 두 개의 포인터를 이동시키면서 진행했습니다. 만약 현재 합이 k보다 작으면 end를 우측으로 이동시키고, 현재 합이 k 보다 같거나 크면 start를 우측으로 이동시키면서 답을 구했습니다.

문제풀이

def solution(sequence, k):
    answer = [0,1000000]
    len_seq= len(sequence)

    # 첫 인덱스의 값이 k일 경우를 위해 end는 -1부터 시작
    start=0
    end=-1
    sum_cur=0

    # 투포인터 알고리즘
    while True :
        # 합이 원하는 값보다 작을 경우 end를 우측으로 한칸 이동
        if sum_cur < k :
            end+=1
            if end == len_seq : break
            sum_cur+=sequence[end]
        # 합이 원하는 값보다 크거나 같을 경우 start를 우측으로 한칸 이동
        else :
            if start == len_seq : break
            sum_cur-=sequence[start]
            start+=1
        # 합이 원하는 값과 일치하고, 기존 answer 의 인덱스 차이보다 작으면 교체
        if sum_cur == k :
            if answer[1]-answer[0] > end-start :
                answer = [start,end]

    return answer

 

https://comhwang.tistory.com/4

[알고리즘] 투 포인터 알고리즘