[Algorithm] 숫자의 표현

프로그래머스 - 숫자의 표현

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 찾는 간단한 문제이다.

첫 오답

function solution(n) {
    var answer = 0;
    
    for(let i=1; i<=n; i++){
        let sum = i;
        if(i === n) {
            answer++;
            break;
        }
        for(let j=i+1; j<n; j++){
            sum += j
            if(sum === n) {
                answer++;
                break;
            } else if(sum > n) break;
        }
       
    }
    return answer;
}

• 테스트 케이스는 통과하였지만 효율성 부분에서 모두 낙제하였다.
• 범위를 줄일 수 있을까?

수정 답안

function solution(n) {
    var answer = 0;
    
    for(let i=1; i<n/2; i++){
        let sum = i;
        for(let j=i+1; j<n/2+1; j++){
            sum += j
            if(sum === n) {
                answer++;
                break;
            } else if(sum > n) break;
        }
       
    }
    return answer+1;
}

⇒ 연속하는 숫자의 덧셈이기에 (에라스토테네스의 체 접근과 유사(?))
첫 for문은 n/2을 넘지 않는 범위까지만, 두 번째 for문은 n/2+1을 넘지 않는 범위까지만 검사!
어차피, 자기 자신은 무조건 답안 케이스로 포함하니 마지막 제출 답안에 +1만 해주면 해결 !