[Programmers / Level2] 연속 부분 수열 합의 개수

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

프로그래머스

---

<내 코드 - 오답>

def solution(elements):
    len_elem = len(elements)
    sums = set()
    for incremental in range(1, len_elem + 1):
        for i in range(len_elem):
            sum_val = 0
            for j in range(incremental):
                sum_val += (elements[(i + j) % len_elem])
            sums.add(sum_val)
                
    return (len(sums))

-> for문을 3번쓰는 O(n^3)의 극악의 효율을 보여준다. 회전을 위해서 division을 통해 값을 set에다 넣어주는 작업을 진행해주었다

 

<정해코드1>

def solution(elements):
    ll = len(elements)
    res = set()

    for i in range(ll):
        ssum = elements[i]
        res.add(ssum)
        for j in range(i+1, i+ll):
            ssum += elements[j%ll]
            res.add(ssum)
    return len(res)

 

<정해코드2>

def solution(elements):
    n = len(elements)
    extended_elements = elements + elements  # 원형 수열을 두 배로 확장
    sums = set()  # 중복을 피하기 위해 집합 사용

    for start in range(n):
        for length in range(1, n + 1):
            sums.add(sum(extended_elements[start:start + length]))

    return len(sums)

-> elements를 두개 더해서 ‘extended_elements’ 라는 배열을 만들어주었다.

나름 직관적이고 실용적인것 같아서 앞으로도 회전순열에서 자주쓸거같다는 생각을 했다.