[프로그래머스] Level 2. 숫자의 표현(JavaScript)

숫자의 표현

문제 설명

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

사고과정

1. 1부터 시작하여 연속적으로 값을 누적합니다.
2. 누적된 값이 만약 n보다 크다면 1부터 누적된 값을 제거합니다.
3. 만약 n보다 작거나 같다면 연속되어 증가하는 값을 계속 더합니다.
4. 이를 위해서 투포인터 방식으로 1부터 제거할 값 firstNum, 1부터 연속적으로 증가할 lastNum을 생성합니다.

1차 코드

function solution(n) {
    var answer = 0;
    let cnt = 1;
    let firstNum = 1;
    let lastNum = 0;
    
    while(lastNum !== n) {
        if(answer > n) {
            answer -= firstNum;
            firstNum++;
            continue;
        }
        if(answer === n) {
            cnt++;
        }
        lastNum++;
        answer += lastNum;
    }
    
    return cnt;
}

결과

효율성 테스트에서 6개 중 5개의 시간 초과 발생으로 실패

1차 코드의 문제점

이 코드에서는 lastNum이 n까지 도달하도록 코드를 구현하면서 필요없는 시간 손실이 발생했습니다.

예를 들어 예시와 같은 15의 값을 기준으로 제가 원하는 계산식을 접근하게 되면, lastNum은 최대 8의 값까지만 가지면 됩니다.

하지만 lastNum이 9, 10, 11, 12, 13, 14까지 증가하면서 firstNum 또한 n보다 작게 만들기 위해 계속해서 값이 늘어나고 반복의 경우가 계속 늘어나기 때문에 이러한 문제가 발생했습니다.

1차 코드의 해결 방안

lastNum의 범위를 Math.ceil(n / 2)으로 제한하여 불필요한 반복의 경우를 제거했습니다.

2차 코드

function solution(n) {
    var answer = 0;
    let cnt = 1;
    let firstNum = 1;
    let lastNum = 0;
    let maxValue = Math.ceil(n/2);
    
    while(maxValue >= lastNum) {
        if(answer > n) {
            answer -= firstNum;
            firstNum++;
            continue;
        }
        if(answer === n) {
            cnt++;
        }
        lastNum++;
        answer += lastNum;
    }
    
    return cnt;
}

결과

테스트케이스 15번 실패

2차 코드의 문제점

테스트케이스 15번은 n = 1 일때 1이 나와야 하는 케이스입니다.

그러나, 제 코드에서 n이 1로 들어오게 되면 maxValue가 1이 되고, lastNum이 첫 반복문 때 1이 됩니다.

이 때, while문의 조건이 true가 되어 불필요한 반복이 1회 더 이뤄지게 되고 if(answer === n) 조건문이 다시 동작되어 cnt가 2가 되는 문제가 있습니다.

2차 코드 해결 방안

임시방편으로 n이 1이라면 1을 return 하는 코드를 추가해서 특수한 테스트케이스의 경우를 해결했습니다.

3차 코드(성공)

function solution(n) {
    var answer = 0;
    let cnt = 1;
    let firstNum = 1;
    let lastNum = 0;
    let maxValue = Math.ceil(n/2);
    
    if(n < 2) return 1;
    
    while(maxValue >= lastNum) {
        if(answer > n) {
            answer -= firstNum;
            firstNum++;
            continue;
        }
        if(answer === n) {
            cnt++;
        }
        lastNum++;
        answer += lastNum;
    }
    
    return cnt;
}

풀이 후기

이렇게 특수한 테스트케이스를 조건 분기로 처리하는건 좋은 코드를 작성하는 방법이 아닌거 같다는 생각을 했습니다.

조건에 맞춰 코드를 점진적으로 수정해나가는 과정은 좋았지만, 알고리즘 자체의 문제가 있다고 생각해서 좀 더 공부해야겠다는 생각을 했고, 가장 보편적이며 깔끔한 정답을 찾아서 공부했습니다.

다른 분들의 해결 방법

function solution(n) {
    var answer = 1;
    let cnt = 1;
    
    n -= cnt;
    while(n > 0) {
        cnt++;
        n -= cnt;
        if(n % cnt === 0) {
            answer++;
        }
    }
    return answer;
}

풀이

수학적 방법을 이용한 풀이인데, 로직은 다음과 같습니다.

1. 어떤 자연수를 연속된 자연수들의 합으로 표현할 때 연속된 자연수들의 개수마다 최대 하나의 경우만 존재한다는 규칙을 이용합니다.

2. n = 15라는 가정하에 n을 두 개의 숫자로 표현하고 싶을 때는 n에서 연속된 숫자 1과 2를 빼고, 결과값인 12를 표현하고 싶은 숫자의 개수 2로 나눕니다.
   12 / 2 = 6 ...0

3. 나머지가 0인 경우에는 몫에다가 연속된 숫자 1, 2를 각각 더합니다.
   6 + 1 = 7, 6 + 2 = 8

4. 대응된 두 값을 더하면 원래 값인 15가 나옵니다.

위 방법을 이용하여 세 개의 숫자로 표현할 때는
15 - [1, 2, 3] = 9
9 / 3 = 3 ...0
3 + 1 = 4, 3 + 2 = 5, 3 + 3 = 6
4 + 5 + 6 = 15
와 같은 구조가 만들어집니다.

하지만 네 개의 숫자로 표현하는 방법은 존재하지 않습니다.
15 - [1, 2, 3, 4] = 5
5 / 4 = 1 ...1

풀이 출처: https://velog.io/@zmdals/%EC%97%B0%EC%86%8D%EB%90%9C-%EC%9E%90%EC%97%B0%EC%88%98%EC%9D%98-%ED%95%A9-2-%EC%88%98%ED%95%99%EC%A0%81%ED%92%80%EC%9D%B4