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

 

문제설명

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/131701

Idea

행의 %N으로 원형 리스트 인덱스를 추출하여 탐색 후 값을 더해줍니다. 

중복된 값이 없어야 하기 때문에 set을 이용하여 부분 수열 합의 값을 저장합니다.

이 때 부분 수열의 합을 구한 값을 재사용합니다. (구했던 값을 굳이 또 다시 구할 필요는 없습니다)

Solution 01

def solution(elements):
    N = len(elements)
    for i in range(N-1):
        elements.extend([elements[i*N+j] + elements[(i+j+1)%N] for j in range(N)])
    return len(set(elements))

부분 수열의 합을 구한 값들을 elements 변수에 추가하며 추가된 변수 값과 기존에 제공된 elements의 값을 더해줍니다.

이후 set으로 변경하여 중복되지 않은 부분 수열 합의 개수를 구합니다.

Solution 02

def solution(elements):
    N = len(elements)
    ans = set(elements)
    add = [e for e in elements]
    for i in range(1,N):
        for j in range(N):
            add[j] += elements[(i+j)%N]
            ans.add(add[j])
    return len(ans)

Solution 01의 접근법과 동일합니다.

다만 01에서 사용한 elements 리스트에 계산된 부분 수열의 합을 추가하는 형식이 아닌,

add라는 리스트를 생성하여 부분 수열의 합을 누적하여 계산합니다.

계산된 값은 set에 바로바로 추가하며 중복되지 않은 부분 수열 합의 개수를 구합니다.

Solution 03

def solution(elements):
    N = len(elements)
    res = set(elements)
    for i in range(N):
        element = elements[i]
        for j in range(i+1, i+N):
            element += elements[j % N]
            res.add(element)
    return len(res)

Solution 02의 접근법과 유사합니다.

다만 02에선 add 리스트를 생성하여 계산된 부분 수열의 합을 갱신하는 방식이 아닌,

i번째 값에 대해 i+1~i+N까지 부분 수열의 합을 계산하여 바로 set에 추가합니다.

이후 중복되지 않은 부분 수열 합의 개수를 구합니다.

03을 사용하여 리스트 인덱스에 접근하는 시간을 줄일 수 있습니다. 

전체 코드는 깃허브에서 확인 가능합니다.