[프로그래머스 Level 2] 숫자의 표현 (JavaScript)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12924

프로그래머스

 

입출력 예

n	result
15	4

 

풀이

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

 

이 코드는 어떤 자연수 n이 연속된 자연수의 합으로 표현될 수 있는 개수를 return 하는 함수이다.

 

외부 for 루프를 통해 i가 1부터 n까지 순차적으로 증가하며, k가 되는 모든 경우를 시도한다.

 

내부 for 루프를 통해 j는 k부터 계속 증가하면서 연속된 숫자를 더한다.

 

sum은 현재까지의 계산된 숫자들의 합이다.

 

sum === n 이면 answer++를 하고 내부 루프를 종료하고,

sum > n 이면 더 이상 j를 증가시키는 것은 의미가 없으므로 내부 루프를 종료한다.

 

하지만!!

효율성 문제로 통과하지 못했다.

 

현재 나의 코드는 최악의 경우 O(n^2) 의 시간 복잡도를 가지고 있다.

 

비록 sum > n 조건에서 일찍 종료되기 때문에 실제 실행시간은 더 짧겠지만, 현재는 그렇다.

 

 

Chat GPT와 함께하는 코드 개선

 

Chat GPT는 이러한 최적화 접근법을 제시했다.

 

연속된 숫자의 합을 구하는 일반식

n=k+(k+1)+(k+2)+⋯+(k+m)

 

이 합은 등차수열의 합 공식을 적용하면 다음과 같다고 한다.

 

여기서 k는 시작 숫자, m+1은 연속된 숫자의 개수.

 

위 식을 변형하여 k를 계산할 수 있는 조건을 찾으면 효율적인 풀이가 가능하다.

 

k가 자연수가 되어야 유효하고, m+1을 증가시키면서 k를 계산하고, k가 자연수인지 확인한다.

 

효율적인 코드

function solution(n) {
    let answer = 0;
    let m = 1;

    while (m * (m + 1) / 2 <= n) {
        if ((n - (m * (m + 1)) / 2) % m === 0) {
            answer++;
        }
        m++;
    }

    return answer;
}

 

여기서 m은 연속된 숫자의 개수를 나타낸다. (m+1).

 

while문의 조건은 연속된 숫자들의 합이 n을 초과하면 계산할 필요가 없음을 의미한다.

 

if문의 식은 n에서 m개 숫자 합을 뺀 나머지가 0이면 k가 자연수임을 체크한다.

 

이 방법은 m의 범의를 O(\sqrt{2n}) 로 줄이므로 매우 빠르게 동작한다.

 

 

최적화된 코드는 O(\sqrt{n}​) 의 시간 복잡도로 작동한다.