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

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

---

 

입출력 예nresult

15

4

---

 

이중 for 문으로 풀었을때 시간복잡도 O(n2) 가 되어 자꾸 탈락하길래 

처음으로 투포인터 알고리즘을 적용해보았는데 

function solution(n) {
    var answer = 0;
    //투포인터 i, j 사이 원소의 합
    let arr = Array(n).fill(0).map((_,i)=> i+1)
    let sum = 0;
    let left = 0;
    let right = 0;
    while(arr[right] <= arr.length){
        sum = arr.slice(left, right + 1).reduce((acc, cur)=> acc + cur, 0);
        if(sum < n){
            right ++;
        }if(sum > n){
            left ++;
        }if (sum === n){
            answer ++;
            left ++;
        }
    }
    
    return answer;
}

너무 화나자나용 ㅜㅜㅜ 

시간 복잡도 너무 어렵다..

---

원소들의 합을 구하기 위해 매번 slice, reduce를 쓰는것이 시간 복잡도를 증가시키는 요인이다

원소 두개의 합이 아니라 left, right 사이에 위치하는 원소들의 합이다 보니 이런 방법을 택했는데 안되겠다 ㅜ

 

[다른 사람 풀이]

function solution(n) {    
    const answer = [];
    let numbers = [];
    let i = 1,
        j = 1;

    while(i <= n){
        numbers.push(i);
        let total = 0;
        for(const num of numbers) total += num;
        if(total === n){
            answer.push(numbers.shift());    // numbers 첫번째 요소만 answer 에 추가             
            i = j++;             // j 할당 후 ++ 
        }else if(total > n){
            numbers = [];
            i = j++;
        }        
        i++;
    }

    return answer.length;
}

 

아니 웃긴게! 이 코드조차 한번 통과되었다가 이후에 다시 작성해보니 시간 초과가 뜬다 ㅋㅋ ㅠ 

질문 올라온거 보니까 이 문제가 시간 복잡도를 빡시게 잡나보다. 

어떤 분이 적어준대로 let 이 아닌 var를 사용하니 시간초과하는 문제 없이 통과했다.

var vs let, const
let, const 는 블록 스코프를 갖기 때문에 if, for와 같이 지정된 블록 영역 내에서 활용될 경우 Lexical Environment 가 새롭게 생성된다. 이 경우 시스템적인 비용이 발생한다.
반면 함수 스코프를 갖는 var 는 이러한 비용적인 측면에서 자유로우므로 성능이 좀더 우세하다
하지만? 이후 브라우저 엔진이 최적화 되면서 케이스에 따라 let 이 더 빠른 성능으로 측정될 때가 있다고 한다. 즉 거의 속도 차이가 없다고 보는것이 맞겠다. 
적어도 프로그래머스 컴파일에서는 유의미한 차이인가보다

 

그리고 코드 중간에 빈 줄이 있으면 또 시간 초과한다 ㅋㅋ ㅋ ㅋ ㅋ재밌네...

지피티 말로는 빈 줄은 실행 성능에 영향을 미치지않는다고 한다.

 

 

또 한가지는

total 을 구할때 누적합이 아닌 reduce를 사용하면 시간 초과로 실패한다.

배열 순회하는건 동일한데, 메서드를 호출하는데서 성능 차이가 발생하나?

 

근데 지금 내 실력은 빈 줄 타령할때가 아니라 문제 해결 능력이 너무 떨어진다는 것임을 잘 알고있다..

 

 

https://blinders.tistory.com/101

[javascript] var가 let보다 빠르다?