[JavaScript] 프로그래머스 코딩테스트 레벨 2 : 숫자의 표현

📌  문제

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

---

📌  풀이

알아야 하는 것

• 슬라이딩 윈도우
  • 연속된 구간 내에서 어떤 조건을 만족하는 부분 구간을 탐색하는 기법

구할 것

• 특정 범위에서의 합

function solution(n) {
    let count = 0;

    for (let start = 1; start <= n; start++) {
        let sum = 0;

        for (let current = start; current <= n; current++) {
            sum += current;

            if (sum === n) {
                count++;
                break; 
            } else if (sum > n) {
                break; 
            }
        }
    }

    return count;
}

처음에는 이렇게 이중 for문으로 문제를 풀었다.

start가 1 ~ 15일 때, 그 안에서 1 ~ 15까지 돌아다닐 수 있는 변수 current를 선언했다.

이 current가 sum에 누적되다가 sum과 같아지면 count++하고 break한다.

만약 current가 누적되다가 sum보다 커진다면 그냥 멈추고 start를 증가시킨다. 

 

즉 1+2+3+4+5 까지 잘 가서 count++를 하고 멈춘 후에는 2+3+4+5... 가 진행된다.

근데 이상하게 return의 개행 하나만으로 시간초과가 떠서 의문이다.

 

**이 코드는 아예 쓸 수 없다!**

 

2번째 풀이는 슬라이딩 윈도우를 사용한 풀이다.

1번 방식이 쭉 누적합을 하다가 목표보다 커지면 멈추고 start를 증가시키는 방법이라면 2번 방식은 경우에 따라 start를 증가시키거나 end를 증가시키는 방법으로 부분 누적합이 이동하는 느낌이다. 크게 보면 비슷하긴 한데 이중 for문을 쓰지 않아도 돼서 시간 복잡도가 훨씬 낮은 편이다. (1번의 경우 값이 클 경우 O(n^2)이다.)

 

function solution(n) {
    let answer = 0;
    let start = 1;
    let end = 1;
    let sum = 1;
    
    while (start <= n) {
        if (sum < n) {
            end++;
            sum += end;
        } else if (sum > n) {
            sum -= start;
            start++;
        } else if (sum === n) {
            answer++;
            end++;
            sum += end;
            sum -= start;
            start++;
        }
    } return answer
}

 

이 문제에서 슬라이딩 윈도우를 사용한 풀이는 시작과 끝의 범위, sum을 1로 초기화한다.

start가 n보다 작거나 같다는 조건으로 while문을 굴릴 때, 경우는 크게 3가지로 나뉜다.

 

1) sum이 n보다 작을 때

이 때는 시작 1은 그대로 두고 끝 범위를 우측으로 가게 해 sum에 더해본다.

예컨대 1, 2, 3, 4, 5처럼 1에 있었던 end가 우측으로 가면서 sum이랑 같을 때까지 sum에 더해주는 것

 

2) sum이 n보다 클 때

이 때는 시작값을 누적합인 sum에서 제외하고 start를 우측으로 이동시킨다.

2, 3, 4, 5, 6은 안된다 -> 3, 4, 5, 6도 안된다 -> 4, 5, 6 된다 

이렇게 2 -> 3 -> 4로 sum에서 기존의 start가 빠진 대신 하나씩 증가한 start가 들어오는 것

 

3) sum === n

이 때는 내가 원하는 부분합이니 answer++ 해준다.

또 다음 값을 봐야 하니 1번처럼 end를 증가시켜 누적합에 더해주고, 2번처럼 start를 증가시켜 누적합에서 제외해준다.

이렇게 하면 start와 end가 어떤 범위에 한해서 같이 이동하게 된다. 

 

1번 코드

2번 코드

 

신기하도다...

유사한 개념으로 투 포인트가 있는데 그건 관련 문제를 풀어보면서 생각해보겠다...

---

**참고

[AL] 투 포인터 알고리즘 (+슬라이딩 윈도우) - JavaScript