[프로그래머스] 숫자의 표현 풀이- JavaScript

문제 출처

Lv.2 숫자의 표현 풀이 - JavaScript

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

문제 설명

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 이하의 자연수 입니다.

입출력 예

n	result
15	4

첫번째 풀이 - BFS 접근(실패)

function solution(n) {
    let answer = 0;
    for (let i = 1; i <= n; i++) {
        let queue = [];
        queue.push([i, i]);

        while (queue.length) {
            const [l, s] = queue.shift();

            if (s === n) {
                answer++;
                break;
            } else if (s > n) {
                break;
            } else {
                queue.push([l + 1, s + l + 1]);
            }
        }
    }
    return answer;
}

이 코드를 실행했지만 아래와 같이 시간초과가 뜨고 말았습니다.
시간 초과의 주된 원인은 큐에 많은 수의 원소가 계속 추가되면서, 그 큐를 처리하는 데 시간이 너무 많이 소요되는 것입니다. 특히 큰 n에 대해서는 큐의 크기가 매우 커집니다.

두번째 풀이 - Two Pointer 접근(성공)

function solution(n) {
    let answer = 0;
    let start = 1, end = 1, sum = 1;

	// start가 n의 절반보다 작거나 같을 동안 아래의 로직을 반복합니다.
    while (start <= (n / 2)) {
    	// sum이 n보다 작다면 end 값을 1 증가시키고,sum에 증가된 end 값을 더합니다.
        if (sum < n) {
            end++;
            sum += end;
        // 만약 sum이 n과 같다면 정답 카운터 answer 값을 1 증가시키고,sum에서 start 값을 빼고,start 값을 1 증가시킵니다. 
        } else if (sum === n) {
            answer++;
            sum -= start;
            start++;
        // 만약 sum이 n보다 크다면 sum에서 start 값을 빼고,start 값을 1 증가시킵니다.
        } else {
            sum -= start;
            start++;
        }
    }
    // 자기 자신 추가
    return answer + 1;
}

start 포인터와 end 포인터는 각각 n/2와 n까지만 이동하므로, 합쳐져서도 n을 초과하지 않습니다. 따라서 투 포인터 방식으로 이 문제를 해결할 때의 시간 복잡도는 선형적인 O(n)이 됩니다.