[프로그래머스] 연속 부분 수열 합의 개수 - ( sum 안 쓰는 방식을 생각하자 )

문제 설명

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다. 그림.png 원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다. 원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

 

 

풀이

def sum_n(arr,n): # n은 1칸씩, 2칸씩, 3칸씩 더하는 값
    num = []
    for i in range(len(arr)-n):
        num.append(sum(arr[i:i+n])) 구간 합을 arr로 반환
    return num

def solution(elements):
    arr_num = []
    
    for i in range(len(elements)+1): # 0개 부터 전체 요소까지 필요
        arr = [t for t in elements]  # arr 생성
        for j in range(i):   
            arr.append(arr[j]) # arr의 앞부분을 n개 만큼 뒤에 덧붙이기
        arr_num += sum_n(arr,i) # i=0일 때 sum_n =[0,0,0,0,0,0]을 반환함
    arr_num = set(arr_num) # set으로 중복값 제거
    arr_num -= set([0]) # 원소 0을 제거

    answer = len(arr_num)
    return answer

통과는 했지만 조건을 추가해서 -= set([0]) 을 없애보자

 

 

def sum_n(arr,n):
    num = []
    for i in range(len(arr)-n):
        if n: # 조건 추가
            num.append(sum(arr[i:i+n]))
    return num

def solution(elements):
    arr_num = []
    
    for i in range(len(elements)+1):
        arr = [t for t in elements]
        for j in range(i):
            arr.append(arr[j])
        arr_num += sum_n(arr,i)
    
    return len(set(arr_num))

하지만 실행속도가 너무 느리다. 다른 사람의 풀이를 봤다.

 

 

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

    for i in range(ll):
        ssum = elements[i]
        print('elements : ',ssum)
        res.add(ssum)    #주어진 값 저장
        for j in range(i+1, i+ll):
            print('ssum : ',ssum)
            ssum += elements[j%ll]  #[7]에 [7,9,1,1,4]를 하나씩 더하는 방식
            res.add(ssum)
    return len(res)

나는 2개씩 더하는 경우에서부터 n개씩 더하는 경우까지 나눠서, 배열을 각각 새로 만들었다.

하지만 이 코드는 [7,9,1,1,4] 에서 원소 하나를 뽑고, 그 원소에 모든 숫자를 순차적으로 더한 뒤 set 집합에 넣었다.

내가 짠 식은 sum 함수가 들어가서 연산이 많이 필요한데, sum을 안 쓰니 속도가 10배는 빨라졌다.

 

 

출처

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

프로그래머스