[프로그래머스] Lv.2 숫자의 표현

Python3, 연습문제

문제

제한 사항

입출력 예시

나의 풀이 (시도)

def solution(n):
    answer = 0
    
    for i in range(1, n+1):
        num = 0
        for j in range(i, n+1):
            num += j
            if num == n:
                answer += 1
                break
        
    return answer

이렇게 하면 정확도는 100%가 나오지만 효율성이 떨어진다.
시간복잡도가 O(n^)이기 때문이다.

주요 포인트

투 포인트 사용이 필요하다

start와 end를 만들어서 start는 고정되어 있고 end만 먼저 끝까지 돈다.
다 돌았으면 배열에서 start를 빼고 end만 하나씩 증가시켜 끝까지 돈다.
만약 부분합(num)이 타겟 넘버와 같아지면 1 증가시킨다.

최종 코드

def solution(n):
    answer = 0
    end = 0
    # 찾고자 하는 부분합
    m = n
    
    num = 0
    
    array = [i for i in range(1, n+1)]
    
    for start in range(n):
        # end를 n까지 이동시키기
        while num < m and end < n:
            num += array[end]
            end += 1
        # 부분합이 m일 때 answer 하나 증가
        if num == m:
            answer += 1
        
        # start 이동시키기
        num -= array[start]
    
    return answer