프로그래머스 / 슬라이딩 윈도우 / 연속 부분 수열 합의 개수

문제

---

 

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

프로그래머스

 

입출력

---

 

해설

---

 

슬라이딩 윈도우을 구현하면 되는 심플한 문제이다.

 

해당 문제의 제한이 elements가 최대 길이 1000이기 때문에

1부터 1000까지 각 길이에 맞게 부분합으로 나올 수 있는 연속 부분합의 가짓수를 세주면 된다.

 

각 길이에 맞춰 O(N)에 작동하니 시간 복잡도는 O(length * length)가 되겠다. 고로 10^6이 최대 시간복잡도라고 할 수 있다.

 

 

정답코드

---

'''
'25. 8. 24

1. 연속 부분 수열의 합
2. 길이가 최대가 1000이기 때문에

스위핑 기법을 이용하면 쉽게 구할 수 있을 것이다.
'''
def solution(elements):
    len_ = len(elements)
    elements = elements + elements

    save_number = set()#이전 숫자들 기억
    
    for length in range(1, len_ + 1):
        front, back = 0, 0
        sum_ = 0
        for p in range(length):
            sum_ += elements[back]
            back += 1

        save_number.add(sum_)#현재 값도 저장
        while front < len_:
            sum_ = sum_ - elements[front] + elements[back]
            front += 1
            back += 1
            save_number.add(sum_)
    return len(save_number)

 

깃허브 : https://buly.kr/4QnmN2d

유튜브 : https://youtu.be/3sEzlbEEA-U