[Programmers/파이썬] 프로그래머스(Lv.2) 연속 부분 수열 합의 개수 문제풀이

문제 설명

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

프로그래머스

 

 

사고 흐름

1. 완전탐색으로 모든 부분 수열의 합을 구해야겠다

2. 원형 수열은 배열을 이어서 붙이면 돼~

 

문제 핵심과 알고리즘

문자열

def solution(elements):
    answer = []
    n = len(elements)
    elements = elements+elements
    for i in range(1, n+1) :
        for j in range(n) :
            answer.append(sum(elements[j:j+i]))
    return len(set(answer))

 

부분 수열의 길이에 대해, 하나씩 이동하면서 합을 구하고 answer에 append한다. 

 

문제 풀면서 헤맸던 부분

 

딱히 없었다

 

총평 

(소요시간: 20분) 어렵지 않았던 문제다. 원형 수열을 어떻게 다룰 것인가만 생각한다면.

그런데 내 코드는 시간 복잡도가 O(n^3)이다. 원래는 부분 수열의 하나의 길이에 대해 배열을 다 돌고, 부분 수열 길이 늘리는 순서로 했는데, sum 과정을 생략하기 위해 특정 시작 인덱스에 대해 부분 수열 길이를 늘려갔다. 

def solution(elements) :
    answer = set()
    n = len(elements)
    elements = elements+elements
    
    for i in range(n) :
        s = 0
        for j in range(n) :
            s+=elements[i+j]
            answer.add(s)
    return len(answer)

 

만약 시간 복잡도가 n^3라면 약간 방향으로 다르게 생각해보자! (for문의 순서를 바꾼다던지..)