programmers - 숫자의 표현

문제 설명

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

1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한사항

∙ n은 10,000 이하의 자연수 입니다.

---

시간초과한 코드

function solution(n) {
    let count = 1;
    let i = 1;
    
    for( let i = 1 ; i <= Math.floor(n / 2); i++ ){
        let sum = i;
        for( let j = i + 1 ; j <= n ; j++){
            sum += j;
            if( sum === n){
                count++;
                break;
            }
        }  
    }
    
    return count;
}

수정된 코드

function solution(n) {
    let count = 1;
    let i = 1;
    
    for( let i = 1 ; i <= Math.floor(n / 2); i++ ){
        let sum = i;
        for( let j = i + 1 ; j <= n ; j++){
            sum += j;
            if( sum === n){
                count++;
                
            }else if( sum > n){
                break;
            }
        }  
    }
    
    return count;
}

1) 반복문 2번을 다 돌게 되면 n이 15여도 시간초과가 발생한다. 따라서 n의 절반 범위만 적절히 잘라서 계산해야 한다.

2) 또한 누적값 sum이 n을 넘어설 때 break를 걸어주어야 더 이상 의미 없는 계산을 멈춰서 메모리 시간을 줄일 수 있다. 이 부분에서 약간의 실수가 있었다.
sum = n인 경우에 break를 걸었던 점이 오류였다.

def solution(n):
    c = 1
    half = (n // 2)
    
    for i in range(1, half + 1):
        total = i
        for j in range(i + 1, n + 1):
            total += j
            if total == n:
                c += 1
            elif total > n:
                break
    
    return c

참고:https://velog.io/@diddnjs02/코딩테스트프로그래머스-숫자의-표현