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

문제 내용

자연수 n 을 연속한 자연수들의 합으로 표현해라.

 

예를 들어,

n = 15 라고 했을 때

15 = 1 + 2 + 3 + 4 + 5

15 = 4 + 5 + 6

15 = 7 + 8

15 = 15

 

이렇게 나타낼 수 있다.

---

전체 코드

function solution(n) {
    // 1
    let result = 0;
    // 2
    let i = 1;
    // 3
    let j = 0;
    
    // 4
    for (; i <= n; i++) {
        if (i * (i + 1) >= n * 2) {
            break;
        }
    }
    
    // 5
    for (; i <= n; i++) {
        // 6
        for (; j < i; j++) {
            // 7
            if (i * (i + 1) == j * (j + 1) + n * 2) {
                result += 1;
                
            // 8
            } else if (i * (i + 1) < j * (j + 1) + n * 2) {
                break;
            }
        }
    }
    
    return result;
}

1. 먼저 결과 값을 저장할 result 생성
2. 반복문에 이용할 i 생성
3. 반복문에 이용할 j 생성
4. 1 부터 i 의 까지의 합은 (i * (i + 1)) / 2 로 표현할 수 있다. 따라서 1 부터 i 까지의 합이 n 보다 크거나 같을 때 까지 반복을 하여 초기 i 값을 찾아준다.
5. 초기 i 값부터 시작하여 i 값이 n 보다 작거나 같을 때 까지 진행한다.
6. j 는 0 부터 시작하여 i 보다 작을 때 까지 진행
7. 만약 (1 부터 i 까지의 합) 이 (1부터 j 까지의 합) + n 과 같다면 result 를 + 1 한다.
8. 그렇지 않고 만약 (1 부터 j 까지의 합) + n 이 더 크다면 break

 

 

n = 15 라고 예를 들면,

 

    // 4
    for (; i <= n; i++) {
        if (i * (i + 1) >= n * 2) {
            break;
        }
    }

(1 부터 i 의 합)이 n 보다 크거나 같을 때 까지 진행한다.

여기서 (1 부터 i 의 합) 은 (i * (i + 1)) / 2 라고 표현할 수 있는데

원래는  (i * (i + 1)) / 2 >= n 이라 표현했지만

읽기 쉽게 양 쪽에 2를 곱하여서 i * (i + 1) >= n * 2 라고 표현했다.

n 은 15 이므로

i * (i + 1) 이 15 * 2 이상 일 때 반복문이 종료된다.

i = 5 일때 값이 30 이 되므로 종료된다.

 

    // 5
    for (; i <= n; i++) {
        // 6
        for (; j < i; j++) {
            // 7
            if (i * (i + 1) == j * (j + 1) + n * 2) {
                result += 1;
                
            // 8
            } else if (i * (i + 1) < j * (j + 1) + n * 2) {
                break;
            }
        }
    }

i = 5 에서 진행을 하고 j = 0 에서 진행을 한다.

i * (i + 1) = 30 이고 j * (j + 1) = 0 이고 n * 2 = 30 이다.

즉, 30 = 0 + 30 이다.

따라서 if 문에 해당하므로 result 를 + 1 한다.

( 1 + 2 + 3 + 4 + 5 = 15) -> (1 ~ 5 까지의 합) - (0 ~ 0 까지의 합)

 

그리고 6 번에 해당하는 반복문으로 돌아와 j 가 + 1 이 되므로 j = 1이 된다.

30 < 1 * (1 + 1) + 30 이므로 8 번 else if 문에 해당한다.

따라서 break 되어 5 번 반복문으로 돌아간다.

 

i = 6 이 되었고 i * ( i + 1 ) = 42 가 되었다.

42 > 2 + 30 이므로 6 번 반복문으로 돌아간다.

 

이렇게 쭉 진행을 하면 j = 3 이 된다.

42 = 3 * (3 + 1) + 30 이므로 result + 1 이 된다.

(4 + 5 + 6) -> (1 ~ 6 까지의 합) - (1 ~ 3 까지의 합)

 

이런 식으로 반복하게 된다.

---

결론

간단한 수학적 개념만 있으면 풀 수 있는 문제.

for 문을 2개를 중첩하여 나이브하게 진행하면 시간 초과가 났음.

따라서 else if 조건을 하나 추가해서 바로 i 에 대한 for 문이 진행되게 하였음.

 

 

출처 : 프로그래머스 연습문제 숫자의 표현
https://programmers.co.kr/learn/courses/30/lessons/12924

코딩테스트 연습 - 숫자의 표현