[홀로 하는 코딩 공부] 연속 부분 수열 합의 개수 (Python)

프로그래머스

사용 언어: Python

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

프로그래머스

 

*** 본 문제를 푸는 과정을 공유하려 한다.

---

▶ 문제 자체가 단순하였기에 풀이 방향도 바로 잡혔다. 작성한 코드는 아래와 같다.

def solution(elements):
    all_set = set()

    for length in range(1, len(elements)+1):
        for start in range(len(elements)):
            summation = 0
            if start+length > len(elements):
                summation += sum(elements[start:len(elements)])
                summation += sum(elements[:start+length-len(elements)])
            else:
                summation = sum(elements[start:start+length])
            all_set.add(summation)

    answer = len(all_set)
    return answer

 

▶ 통과다. 하지만 테스트 케이스에서 시간이 많이 소요되는 것을 확인할 수 있다. 위 코드대로 작성하면서도 배열의 일부 합을 계산하는 부분에서 시간이 많이 소요되지 않을까 싶었다. 해당 부분 때문에 시간이 많이 소요되었을 거라고 생각하여 해당 부분을 수정했을 때 시간이 덜 소요되는지 확인하기 위해 코드를 일부 수정해보려한다.

▶  배열의 일부를 매번 summation하게 되면 시간이 많이 소요되기에 배열의 일부 합을 저장해놓는 배열을 선언한다. 그리고 매번 계산하지않고 일부 합을 저장해놓은 배열에서 값을 가져오는식으로 코드를 작성한다.

def solution(elements):
    all_set = set(elements[:])

    dp = [elements[0]]
    double_elements = elements * 2

    for i in range(1, len(double_elements)):
        dp.append(dp[i - 1] + double_elements[i])

    for length in range(2, len(elements)):
        all_set.add(dp[length - 1])
        for j in range(length, length + len(elements) - 1):
            all_set.add(dp[j] - dp[j - length])

    all_set.add(dp[len(elements) - 1])
    answer = len(all_set)
    return answer

 

 

▶ 시간이 대폭 줄었다! 다음부터 시간이 덜 걸리는 방향으로 코드를 처음부터 작성하기 위해서 해당 부분을 바로 떠올리도록 연습을 해야겠다.

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.