LV 2: 연속 부분 수열 합의 개수

문제 링크

LV 2: 연속 부분 수열 합의 개수

구현 방식

• 완전 탐색으로 풀어주었다

• 처음에는 3중 for문으로 구현해주었는데, elements의 길이가 1000 이하여서 TLE를 받았다

• 아래와 같은 방식으로 2중 for문으로 해결할 수 있다

• elements를 인덱스 0부터 순회하면서, sum_set에 연속 부분 수열 합을 add 해주는 방식으로 구현해주었다

  • 인덱스 0부터 시작
    -> tmp_sum에 elements[i]를 할당해주고 sum_set에 tmp_sum을 add
    -> for j in range(i+1, i+N):을 순회하며 tmp_sum += element[j]를 해주고 매 회마다 sum_set에 tmp_sum을 add
    -> (원형 수열이기 때문에 j가 N미만일 때와 이상일 때를 구분해주어야 한다)
  • len(sum_set)이 구하고자 하는 정답이 된다

코드

def solution(elements):
    N = len(elements)

    sum_set = set()
    for i in range(N):
        tmp_sum = elements[i]
        sum_set.add(tmp_sum)
        for j in range(i+1, i+N):
            if j < N:
                tmp_sum += elements[j]
            else:
                tmp_sum += elements[j-N]
            sum_set.add(tmp_sum)
    return len(sum_set)
    
    # sum_set = set();
    # for length in range(1, N+1): #길이가 length인 연속하는 부분 수열의 합
    #     for i in range(N):
    #         tmp_sum = 0
    #         for j in range(i, i+length):
    #             if j < N:
    #                 tmp_sum += elements[j]
    #             else:
    #                 tmp_sum += elements[j-N]
    #         sum_set.add(tmp_sum)
    # return len(sum_set)