[기초 Lv.1] 숫자의 표현

오답노트 24번

1. 문제 (링크) :

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

1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

2. 내가 푼 방법 (맞음 but 시간 초과 발생):

: 풀이는 맞는데 시간초과로 실패한 것들이 있었다.

function solution(n) {
    let count = 0, sum = 0, start = 1, end = 1;
    while (start <= n) {
        if (sum < n) {
            sum += (start++);
        } else if (sum > n) {
            sum -= (end++);
        } else {
            count++;
            sum += (start++);
            sum -= (end++);
        }
    }
    return count + 1;
}

3. 시간 초과 해결한 풀이:

1) sum += (start++);
2) sum -= end;end++;
1번에 2번으로 바꿔줬다고 시간 초과로 실패했던 풀이가 해결이 됐다...

그 이유는
1. 연산자 오버헤드:

• 1번의 경우 임시 변수를 만들어 원래값을 저장하고, 그 후에 값을 증가시키는 추가적인 작업이 필요
• 2번의 경우 먼저 값을 더한 후, 별도로 값을 증가시켜서 임시 변수를 사용하지 않음

sum += (start++);
1. sum에 start의 현재 값을 더한다.
2. 임시 변수를 생성하여 start의 현재 값을 저장한다.
3. start 값을 증가시킨다.

sum += start; start++;
1. sum에 start의 현재 값을 더한다.
2. start 값을 증가시킨다.

2. 최적화 가능성:
   내가 보기엔 1번이 코드 줄수를 줄였기 때문에 효율적이라고 생각했지만,
   2번이 더 단순한 코드이며 컴파일러가 최적하기 쉽다고 한다.

function solution(n) {
    let count = 1, sum = 0, start = 1, end = 1;
    while (start <= n) {
        if (sum < n) {
            sum += start;
            start++
        } else if (sum > n) {
            sum -= end;
            end++
        } else {
            count++;
            sum += (start++);
            sum -= (end++);
        }
    }
    return count;
}

4. 챗지피티 도움

링크