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

문제

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

프로그래머스

문제 설명

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

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

제한사항

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

입출력 예

입출력 예 설명

입출력 예 #1
길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있습니다.
길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있습니다.
길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있습니다.
길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있습니다.
길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있습니다.
이들 중 중복되는 값을 제외하면 다음과 같은 18가지의 수들을 얻습니다.
[1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22]

 

풀이

이 문제는 원형으로 가장 끝값과 처음 값이 연결되어 있다는 것을 잘 기억해야 한다.

문제를 푼 방식은 다음과 같다.

1. 기존 리스트를 복사해 temp_e 변수에 저장한다.

2. temp_e에서 n개씩 묶어 합을 구할텐데, 뒤에 가장 끝 요소와 연결되는 원소들을 미리 붙여준다.

예를 들어, n이 3이라면 3개씩 묶을 수 있다.
7, 9, 1, 1, 4에서 4, 7, 9가 나올 수 있으므로 미리 7, 9를 뒤에 붙여준다.
그래서 다음과 같이 정리할 수 있다.
i) n = 2 인 경우, 7, 9, 1, 1, 4 => 7, 9, 1, 1, 4, 7
i) n = 3 인 경우, 7, 9, 1, 1, 4 => 7, 9, 1, 1, 4, 7, 9
i) n = 4 인 경우, 7, 9, 1, 1, 4 => 7, 9, 1, 1, 4, 7, 9, 1
이렇게 미리 붙여 넣은 배열을 다시 만들어주면, 쉽게 합을 구할 수 있다.

 

3. find_case라는 함수를 만들어 n개씩 묶어 나올 수 있는 합을 구한다.

 

정답 코드

위 순서대로 구현하면 다음과 같이 구현할 수 있다.

def solution(elements):
    fin_list = [] # 최종적으로 발생한 모든 합을 저장할 리스트형의 변수
    fin_list += elements # 1개씩 묶는 경우, 기존 리스트의 각 요소가 들어가므로 추가
    fin_list.append(sum(elements)) # 가장 마지막의 경우, 모든 요소의 합이 되므로 미리 추가
    
    # 반복문으로 2개씩, 3개씩, .. 전체개수-1개씩 묶었을 떄 나오는 합을 구한다.
    for i in range(2, len(elements)) :
    	# find_case에서 반환된 값을 리스트에 추가한다.
        fin_list += find_case(i, elements)
    return len(set(fin_list)) # 중복을 제거해야 하므로, set으로 변환한 뒤 길이 출력

# n개씩 elements를 묶었을 때 나오는 합의 경우들을 반환하는 함수이다.
def find_case(n, elements) :
    temp_e = elements.copy() # 복사하지 않으면 기존 elements까지 바뀌므로 copy()한다.
    sum_list = [] # 반환하기 위한 합들을 저장하는 리스트형 변수
    for i in range(n-1) : # 끝 요소와 연결되는 앞부분의 요소들을 미리 뒤에 붙여준다.
        temp_e.append(elements[i])
    for i in range(len(temp_e)-n+1): # 반복문으로 n개씩 묶어 합을 구한다.
        temp = temp_e[i:i+(n%cnt)]
        sum_list.append(sum(temp))
    return sum_list

 

코드와 옆에 있는 주석을 차근차근 읽으면 이해에 많은 도움이 될 것이다.

물론 이렇게 푸는 사람들은 거의 없었지만, 도움이 되었기를..!