[프로그래머스/js] 숫자의 표현 (Lv. 2)

문제

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

프로그래머스

프로그래머스 :: 숫자의 표현 :: Lv. 2

문제 리뷰

이번에 pick 한 문제도 문제 설명이 짧고, 스토리텔링이 더해지지 않아(군더더기 없는 설명!!) 이해가 쉬운 문제였습니다.

 

저는 일단, "그냥 1부터 '연속된 자연수의 합'이 n이 되는 애들 수집해버려" 라고 생각했고, 그렇게 코드를 작성했습니다.

 

(Stay..)

 

첫 번째 시도 (오답, 79.2/100)

code

function solution(n) {
    let answer = [];
    
    for (let i = 1; i <= n; i++) {
        let temp = []; // 임시 배열
        let tempTotal = 0;
        let j = i;
        
        while (tempTotal < n) {
            temp.push(j++);
            tempTotal = temp.reduce((acc, cur) => acc + cur, 0);
            
            if (tempTotal === n) {
                answer.push(temp);
                break;
            }
        }
    }
    
    return answer.length;
}

review

ㅋ.

 

정확성 테스트는 모두 통과했지만, 효율성 테스트에서 참패한 모습입니다.

 

한 번 패하고 나니 번쩍!! 생각이 떠오르더군요..

 

— 이건 누적합 배열과 함께라면 해결할 수 있어.. —

 

두 번째 시도 (오답, 87.5/100)

code

function solution(n) {
    let sumArr = [0];
    let answer = 0;
    let [l, r] = [0, 1];
    
    for (let i = 1; i <= n; i++) {
        sumArr.push(sumArr[sumArr.length - 1] + i);
    }
    
    while (l < r && l <= n && r <= n) {
        if (sumArr[r] - sumArr[l] > n) l++;
        else if (sumArr[r] - sumArr[l] < n) r++;
        else {
            answer++;
            l++;
            r++;
        }
    }
    
    return answer;
}

review

ㅋ. (2)

 

그러나 이번에도 실패

 

하지만 첫 번째 시도에 비해 효율성에서 제법 성과를 얻은 모습입니다.

이런 방법을 two-pointers 라고 하던가요?

누적합 배열이라는 아이디어 자체는 나이스 한 것 같네요..

 

그렇다면 이제 손 볼 곳은 뭐냐?

while을 뚫어져라 바라봅니다..

 

세 번째 시도 (정답)

code

function solution(n) {
    let sumArr = [0];
    let answer = 0;
    let [l, r] = [0, 1];
    
    for (let i = 1; i <= n; i++) {
        sumArr.push(sumArr[sumArr.length - 1] + i);
    }
    
    while (l <= n && r <= n) { // `l < r` 조건 삭제
        const sub = sumArr[r] - sumArr[l]; // 중복 연산 방지
        
        if (sub > n) l++;
        else if (sub < n) r++;
        else {
            answer++;
            l++;
            r++;
        }
    }
    
    return answer;
}

review

미묘한 수정 결과, 통과할 수 있었습니다!!

 

소감

첫 번째 시도 (오답, 79.2/100)	두 번째 시도 (오답, 87.5/100)	세 번째 시도 (정답)

 

음.. 좋았어

 

레벨1 문제들을 풀 때는 대부분

답이 나오기만 하면 됐는데,

 

레벨2 부터는 시간복잡도를 유의하면서 계획하는 연습을 해야할 것 같습니다.

 

---

(+) let에서 var로 바꾸기만 했는데..

그런데 말이죠

질문하기에 들어가 보니 이런 질문이 있더군요.

..뭐라구요?!?!

그래서 두 번째 시도의 코드에서, 모든 let을 var로 바꿔 보았는데..

 

이게 되네

 

구글링 해보니, 'var와 let 간 성능 차이'에 대해 이미 수많은 분들이 의문을 제시하셨고, 또 분석하신 게시글이 있었습니다.

 

요약하자면

1. 일부 케이스에서는 let이 빠르지만, 또 어떤 케이스에서는 var가 빠르더라
2. 그 이유는, Scope와 Lexical Enviroment 간 관계의 차이에서 비롯된 것으로 추정된다
3. (개발 환경에서는) var보단 let을 쓰자

입니다.

 

자세한 내용을 공부하고자 한다면

1. var와 let 간 성능 차이
2. var let const
3. js scope
4. js lexical enviroment

등의 키워드를 검색해 보면 되겠습니다.