[파이썬] 프로그래머스 연속 부분 수열 합의 개수 풀이

문제 확인

프로그래머스

나의 풀이

• 성분의 개수($n$)을 늘려가며 부분 수열을 구성하면 되는 문제다.
• 끝점의 index가 범위를 초과할 경우를 처리해주는 것이 중요하다. 
• 범위 초과 시 위 그림과 같이 표현할 수 있기 때문에 각 수열을 나눠서 합했다.  

def solution(elements):
    sum_unique = set()
    # 성분 개수
    for n in range(len(elements)):
        # 시작점
        for i in range(len(elements)):
            # 배열의 길이 초과할 경우
            if n + i > len(elements):
                e_sum = sum(elements[i:]) + sum(elements[:i + n - len(elements)])
            else:
                e_sum = sum(elements[i:i + n])
            sum_unique.add(e_sum)
    return len(sum_unique)

다른 사람 풀이

회전 큐를 사용한 풀이

• 매 회전 마다 부분 합을 따로 구하게 되면, 결국 전체 부분합 경우를 모두 고려할 수 있다.
• deque.rotate(1) == list[i:] + list[:i]

from collections import deque

def solution(elements):
    answer = set()
    elements = deque(elements)
    for j in range(len(elements)):
        elements.rotate(1)
        for i in range(1,len(elements)):
            answer.add(sum(list(elements)[:i]))
    answer.add(sum(elements))
    return len(answer)

범위 초과하는 리스트 인덱싱 쉽게 하는 방법

• 리스트를 연결하면 된다!

def solution(elements):
    result = set()
    
    elementLen = len(elements)
    # [7, 9, 1, 1, 4, 7, 9, 1, 1, 4]
    elements = elements * 2
    
    for i in range(elementLen):
        for j in range(elementLen):
            result.add(sum(elements[j:j+i+1]))
    return len(result)

 

---

참고

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

 

프로그래머스