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

문제 풀이

function solution(n) {
  var answer = 1;
  let lt = 1;
  let sum = 0;
    for(let rt = 1; rt<n; rt++){
        sum += rt
        if(sum === n) answer++
        while(sum > n){
            sum -= lt++
            if(sum === n) answer++
        }
    }
    return answer
}

 

• 반복문을 이용하여 rt(right)를 sum에 누적하여 더하고 sum에 값이 변할 때마다 조건문으로 sum 값을 확인합니다.
• sum 값이 n값보다 클 경우 sum  - lt(left)를 sum 값에 넣어준 후 lt의 값은 증가시킵니다.
• sum에 값이 변했으므로 다시 조건문으로 sum 값을 확인합니다.

수열에 누적 합이 특정값을 넘게 되면 처음 값들을 빼면서 특정값을 찾는 방식을 사용했습니다.

특정 값이 6이라 할 때 1 2 3 4 5 6이라는 수열이면 반복문에 rt를 이용해 하나씩 누적하여 더해 간다.

1+2, 1+2+3... 여기서 1+2+3은 6이므로 특정값에 만족하여 카운트를 올려준 후 다시 반복문으로 1+2+3+4로 진행되면 누적값이 6 초과이기 때문에 lt값을 계속 빼주면서 특정값을 찾는다.

그러면 해당 식이 생성되는데 (1+2+3+4) - 1 이 식은 초기 1 값을 뺀 2+3+4를 의미하고 다시 (2+3+4) - 2는 3+4를 의미한다.

이런 식으로 lt를 이용해 값을 빼주면서 값을 찾아나가는 방식으로 두 개의 위치(rt, lt)를 기록하며 처리하기 위해 투포인터 알고리즘을 사용하였습니다.