[TIL] 2023.09.10 Programmers_숫자의 표현

숫자의 표현

문제 설명

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현하는 방법이 여러 개라는 사실을 알게 되었습니다. 예를 들어 15는 다음과 같이 4가지로 표현할 수 있습니다.

• 1 + 2 + 3 + 4 + 5 = 15
• 4 + 5 + 6 = 15
• 7 + 8 = 15
• 15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해 주세요.

 

---

나의 1차 풀이

function solution(n) {
    const arr = Array(n).fill(0).map((_, idx) => idx + 1);
    let count = 0;
    
    for (let i = 0; i < n; i++) {
        arr.slice(-i).reduce((acc, cur) => {
            acc += cur;
            if (acc === n) count++;
            // if (acc > n) break;
            return acc;
        }, 0)   
    }
    return count;
}

1부터 n까지를 요소로 가지는 배열을 생성한 후 for문으로 각 숫자를 순회하며 `reduce()` 메서드로 값을 누산해서 15가 나오면 count에 1씩 더해주는 방식으로 접근했다.

 

`acc === n`이라는 if문의 조건을 충족했다면 `reduce()` 연산을 계속하는 것은 불필요한 실행이므로 break를 이용해서 끊어주려고 했는데  `reduce()`에서는 break를 사용할 수 없다고 한다. 일단 break 코드에서 에러가 떠서 이 부분을 주석 처리하고 풀이를 제출해 본 결과 정확토 테스트는 모두 통과했지만 효율성에서 실패했다. 그래서 `reduce()`에서 break를 사용할 수 있는 방법을 검색해 봤다.

 

 

나의 2차 풀이

function solution(n) {
    const numArr = Array(n).fill(0).map((_, idx) => idx + 1);
    let count = 0;
    
    for (let i = 0; i < n; i++) {
        const slicedArr = numArr.slice(-i);
        slicedArr
        	.slice(0) // slice(0)하여 array를 그대로 복사된다.
            	.reduce((acc, cur, _, arr) => {
                    acc += cur;
                    if (acc === n) count++;
                    // 인덱스 1 이후의 모든 요소를 삭제한다. 따라서 더이상 순회할 요소가 없어서 break되는 원리이다
                    // 다만 기존 배열이 삭제될수 있으니 첫번째단계에서 slice(0)로 배열을 복사한 이유가 이것이다.
                    if (acc > n) arr.splice(1); 
                    return acc;
                }, 0)   
    }
    return count;
}

`reduce()`에는 일반적인 break 문법을 사용할 수 없다고 한다. 대신 원본 배열을 `splice()`해서 인덱스 0인 요소 하나만 남게 배열을 변경하여 더 이상 순회할 요소가 없게 만드는 방식으로 break 기능을 구현할 수 있다.

 

`splice()`를 이용해서 `reduce()`의 누산값, 즉 acc가 15를 초과했을 때 `reduce()`를 종료하게 수정했지만 여전히 효율성을 통과하지 못하고 있다. 아무래도 접근 방식 자체를 바꿔야 할 거 같다.

 

참고

https://stackoverflow.com/questions/36144406/how-to-early-break-reduce-method

https://inpa.tistory.com/entry/JS-%F0%9F%9A%80-reduce-break-%ED%95%98%EB%8A%94-%EB%B2%95-How-to-early-break-reduce

 

 

나의 3차 풀이

function solution(n) {
    let count = 0;
    for (let i = 1; i <= n; i++) {
        let sum = 0;
        for (let j = i; j <= n; j++) {
            sum += j;
            if (sum === n) count++;
            if (sum > n) break;
        } 
    }
    return count;
}

이중 for문을 사용하는 방법으로 바꿔봤다. 기본 접근 방식과 비슷한데 사용하는 메서드를 줄이고 좀 더 간결한 코드를 작성해 봤다. `Array()`로 배열을 새로 생성한다든가, for문을 돌며 `slice()`를 두 번에 걸쳐 생성하는 등의 연산 시간을 줄여 효율성 테스트를 통과하고자 했다. 결과적으로는  효율성 테스트 6개 중에 4개 통과했다. 점점 정답에 가까워지고 있다..!

 

 

나의 최종 풀이

function solution(n) {
    let count = 0;
    for (let i = 1; i <= n; i++) {
        let sum = 0;
        for (let j = i; j <= n; j++) {
            sum += j;
            if (sum === n) {
                count++;
                break;
            }
            if (sum > n) break;
        } 
    }
    return count;
}

3차 풀이에서 for문 내부의 첫 번째 if문에 `sum === n`일 때 break를 추가했더니 효율성 테스트까지 완전히 통과할 수 있었다! 이렇게 여러 번 수정을 거듭하면서 더 효율적인 방법을 고민하고 정답에 가까워지는 과정이 코딩테스트의 재미인 거 같다. 😇