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

✏️ 문제

풀이

💡 우선 순위 큐같은 모양이라서 힙으로 풀어야 하나? 고민했다

하나의 인덱스에서 시작해서 길이를 늘려가면서 더하려고 했는데, 생각을 잘못한 게 길이를 늘릴 때마다 매번 start에서 다시 시작해서 값을 더하고를 반복하려다보니 반복문이 무한대로 늘어났다. for문 중첩이 한 3개 정도 됐음

그래서 그냥 elements라는 배열을 하나 더 이어붙여서 인덱스 계산 안 해도 되게끔 편하게 했는데 시간이 ㅎ... 코드 못 짜서 메모리 두 배로 쓰는 멍청한 짓을 해버림

🕐 시간 과다 코드

def solution(elements):
    L = len(elements)
    
    elements += elements
    answer = set()
    
    for start in range(L):
        for next_index in range(start, start+L):
            answer.add(sum(elements[start:next_index+1]))
        
    return len(answer)

통과못하는줄 ㅎㅋ

⭕️ 효율적인 코드

배열의 값이 [7, 9, 1, 1, 4]로 주어졌고 시작 값이 네번째 1이라고 했을 때,

1️⃣ 1을 먼저 answer에 추가
2️⃣ sum_seq을 1로 초기화
3️⃣ sum_seq에 다음 값 4를 더하고 answer에 추가
4️⃣ sum_seq에 다음 값 7을 더하고 ...
5️⃣ sum_seq에 다음 값 9를...
...

이런 식으로 하나씩 더하면서 바로바로 추가하면 된다.

def solution(elements):
    L = len(elements)
    
    elements += elements
    answer = set()
    
    for start in range(L):
        for next_index in range(start, start+L):
            answer.add(sum(elements[start:next_index+1]))
        
    return len(answer)

1/10로 줄어듦