[프로그래머스][JS] 숫자의 표현 ✅

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

프로그래머스

풀이 과정

function solution(n) {
    let cnt = 0 // sum과 n이 같을 경우 카운트할 변수
    let sum = 0
    let start = 1
    let end = 1
    while(start <= n){ // start가 n보다 작을 경우에만 반복하기
        if (sum < n){ // sum이 n보다 작을 때
            sum += end // sum에 end 더하고
            end++ // end에 +1: 끝점을 한 칸 앞으로
        }else if (sum === n){ // sum과 n이 같을 때
            cnt++ // 카운트 +1
            sum -= start // sum에서 start값을 빼기
            start++ // start += 1: 시작점을 한 칸 앞으로
        }else{ // sum > n
            sum -= start // sum이 n보다 클 때
            start++ // start += 1: 시작점을 한 칸 앞으로
        }
    }
    return cnt
}

주어진 자연수 n을 연속된 자연수들로 표현하는 방법의 수를 구하기 위해 모든 가능한 경우를 탐색하는 완전 탐색 알고리즘 방법으로 구현을 했다.

시간 복잡도는 O(n)

 

---

리뷰

처음에 투 포인터 알고리즘을 이용하여 풀었더니 한 개의 히든 케이스에서 시간 초과가 발생했다

그래서 연속된 자연수들의 합이 자연수 n과 같아질 때까지 연속된 자연수들을 더하는 방식으로 문제를 해결했다