프로그래머스 - 연속 부분 수열 합의 개수

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

프로그래머스

두개의 선택지가 존재한다.

 

1. 정석대로 인덱싱을 통해 순회하기

2. 최대 한바퀴까지만 탐색하니까 배열을 하나 똑같이 붙이기

 

1번으로 하게 되면 순회와 조건문 연산을 해야하니까 시간은 더 오래걸리지만 요구 메모리는 줄어들고

2번으로 하게 되면 메모리는 더 소요되지만 속도가 더 빠르다.

 

저번에 백준에서 1번으로 풀었으니까 이번엔 2번으로 하기로 했다.

 

1. 똑같은 배열은 똑같이 붙인다.

2. visited를 활용하여 중복되는 answer을 줄이고자 하였다.

3. i는 몇번 더할 것인지를 나타내고 j는 인덱스를 나타낸다.

3-1. 미리 구한 길이만큼만 순회하며 sum을 진행하고

3-2. visited에 없다면 추가해주면서 cnt를 1 더한다.

def solution(elements):
    answer = 0
    
    length = len(elements)
    elements = elements + elements
    
    visited = {"cnt":0}
    
    for i in range(length):
        for j in range(length):
            sum_result = sum(elements[j:i+j])
            if visited.get(sum_result):
                pass
            else:
                visited[sum_result] = 1
                visited["cnt"] += 1
    
    answer = visited["cnt"]
    
    
    return answer