[프로그래머스] 파이썬 문제풀이 - 점프와 순간 이동

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

프로그래머스

첫 풀이

1. 편한 탐색을 위해 배열을 한 번 더 붙여준다

2. 뽑을 길이를 제어해줄 for문을 만든다 ex)길이 1인 부분수열만들지, 2인 부분수열만들지

3. 수열을 추출할 인덱스를 시작할 for문을 만든다 ex) 길이 2인 부분수열 만들 때 [0:2] 할지 [1:3]할지

 

def solution(elements):
    s1 = set()
    n=len(elements)
    elements=elements+elements
    for i in range(1,n+1):
        for j in range(n):
            s1.add(sum(elements[j:j+i])) 
    answer=len(s1)
    return answer

통과는 하긴했지만 시간과 메모리를 많이 사용한다

더 나은 답안

1. 배열을 늘리지 않고 mod를 사용하면 메모리를 절약할 수 있다

2. 중간에 sum을 저장해두고 하나씩 더해간다

def solution(elements):
    n = len(elements)
    s1 = set()

    for i in range(n):
        ssum = elements[i]
        s1.add(ssum)
        for j in range(i+1, i+n):
            ssum += elements[j%n]
            s1.add(ssum)
    return len(s1)

 

배운 점

1. 배열을 sum하는것보다 중간에 sum을 저장해두고 하나씩더해가면서 풀면 시간을 줄일 수 있다