문제 설명

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

• 1 + 2 + 3 + 4 + 5 = 15

• 4 + 5 + 6 = 15

• 7 + 8 = 15

• 15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

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

일단 코드가 생각나는데로 직관적으로 풀었으나 시간복잡도 측면에서는 고려해야할 부분이 많다. 슬라이딩윈도우(투포인터)로 다시 풀어봤다

def solution(n):
    answer = 0
    
    left, right = 1,1
    total = 1
    
    while left <= n :
        if total == n :
            answer +=1    
            # n = 6
            # 123
            # answer +=1
            # left를 하나 올림 2,3
            # total 기존 left만큼 제외.
            total -= left
            left +=1
        elif total < n :
            right += 1
            total += right
        else : # total > n 
            total -= left
            left +=1
    
    return answer

처음엔 range 함수로 sum을 산출했는데 그렇게 푸니 O(n2) 가 나온다고 해서 total로 풀었다.