[65일차][Lv2][프로그래머스][131701]연속 부분 수열 합의 개수

문제 설명

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

3 ≤ elements의 길이 ≤ 1,000
1 ≤ elements의 원소 ≤ 1,000

 

입출력

elements	result
[7,9,1,1,4]	18

 

코드 및 설명

def solution(elements):
    len_elements = len(elements)
    elements = elements * 2        
    check_arr = []
    
    for idx1 in range(1, len_elements+1):
        for idx2 in range(len_elements):
            #if idx1+idx2 > len_elements:
            #    check_arr.append(sum(elements[idx2:idx1+idx2]))
            #else:           
            check_arr.append(sum(elements[idx2:idx1+idx2]))
            
    return len(set(check_arr))

이 문제는 elements의 길이만큼 반복하면서 한 개 묶음의 합, 두 개 묶음의 합... elements길이만큼의 합을 만드는 데 그 개수가 몇개인지를 알아내는 것이다. 원형 수열이기 때문에 elements * 2를 하여 원형 수열의 형태로 만들어줬고, elements * 2를 해도 결국 elements의 길이만큼 돌기 때문에 문제될 부분은 없다. 처음 문제를 풀 때 코드를 보면

if idx1+idx2 > len_elements:                 check_arr.append(sum(elements[idx2:idx1+idx2]))

이 부분이 있는 데 elements * 2를 해주기 전 어떻게 하면 원형 수열처럼 만들어 줄 수 있을 까 하다가 elements의 길이를 넘으면 뭔가를 해주려고 했다가... 다시 생각해보니 elements * 2를 해주면 해결될 것 같아 수만 변경하고 그대로 남겨놓아버렸다............필요없는 건데...하하하... 하지만 뭔가 위 코드로 돌렸을 때 너무 오랜 시간이 걸리는 것 같아서, 리팩토링을 해보려한다.

def solution(elements):
    len_elements = len(elements) 
    check_set = set()

    for idx1 in range(len_elements):    
        set_sum = elements[idx1]
        check_set.add(set_sum)
        for idx2 in range(idx1+1, len_elements+idx1):
            set_sum += elements[idx2%len_elements]
            check_set.add(set_sum)
            
    return len(check_set)

위에 코드로 리팩토링 해보았다.

check_set에 set() 함수 넣어 놓고, elements 길이만큼 for문을 돌리는 데

 set_sum = elements[idx1] <-- elements의 첫번째 배열을 check_set에 넣어놓고, 다음 for문에서 idx1이 0이니까 idx1+1부터 elements + idx1을 도는데, 처음 [7,9,1,1,4] 중 7이 check_set안에 저장되어있고, idx2%len_elements를 0이기 때문에 같은 수인디 7이 저장되지만 set()이기 때문에 중복제거가 될 것이다. 이것이 반복되면서 돌면 중복제거하면서 저장된 합이 check_set에 남게 되고 이것의 길이를 반환하면 정답이 되게 된다. 위에 코드보다 확실히 빨라진 걸 볼 수 있다.