프로그래머스 숫자의 표현 자바스크립트 문제 풀이

문제 설명

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부터 시작해서 n의 숫자만큼 순서대로 더해가며 계산을 하려고 했다.

코드는 완성했고 테스트는 모두 통과했지만.. 효율성에서 모두 실패하였다.. 왜그럴까?

 

이 문제에서 원하는 답은 수학적인 방법으로 코드를 완성해야했다.

 

 

효율성에서 실패한 문제 풀이

function solution(n) {
  let result = 0;
  let answer = 0;
  let arr = Array.from({ length: n }, (e, i) => i + 1);

  while (arr.length > 0) {
    for (let i = 0; i < arr.length; i++) {
      answer += arr[i];
      if (answer === n) {
        result += 1;
        break;
      }
    }
    answer = 0;
    arr.shift();
  }
  return result;
}

- 우선 arr에 배열을 넣어주었다. from메서드를 통해서 i에 1을 더해가면서 n의 길이만큼 배열을 만들어 넣어주었다.

- 그리고 while문을 반복하면서 answer에 arr[i]값을 더해가며 n이 되는 경우를 result에 count한다.

- 만약 n값과 같아지면 즉시 break를하고 answer는 다시 0으로 만들어준다 그리고 arr에서 shift를 통해서 하나씩 빼준다.

- 그렇게하면 모든 경우의 수를 순회하면서 연속된 자연수의 더한 값이 n과 같은지 알 수 있다.

- 역시나 효율성에서 실패하였다..... 근데 의문 여기서 효율성으로 어떻게 줄여야할까?

- 문과인 나는 이러한 수학공식을 들어본적이 없는데 있는건가..?!

---

---

공식이라고 하기 뭐하지만 아무튼 신기한 수학공식이 있었다.

만약 연속된 두개의 수로 n값을 만든다고 쳐보겠다.

 

n = 15;

 

1 + 2 이 순차적인 1과  2가 있다.

1 + 2는 3이다.

15 - 3을하고 12이다.

12를 2로 나누어주면 6이다.

1, 2 에 6을 각각 더해준다.

그럼 7, 8이 나온다.

7 + 8은? 값은 15이다.

 

1 + 2 + 3 이면?

15 - 6 = 9

9 / 2 = 3

1, 2, 3 에 3을 각각 더해주면? 4, 5, 6이 나온다.

4 + 5 + 6 = 15

 

신기하다... 이걸 한번더 생각해서 보면

1 + 2 + 3 + 4 + 5 + 6 ...

앞에 값인 1을 15에서 빼준다.

14 = 2 + 3 + 4 + 5 그럼 1, 2, 3, 4, 5로 15를 만들 수 있는 걸 알 수 있다.

그 뒤에 1 + 2 를 15에서 빼준다.

12 = 3 + 4 + 5, 그럼 또 1, 2, 3, 4, 5로 15를 만들 수 있다.

거기에 또 1 + 2 + 3 을 15에서 빼준다.

9 = 4 + 5, 앞에서 1 + 2 + 3이 들어가있는게 되기 때문에 연속적으로 값을 빼면서 맞는지 확인할 수 있다.

그렇게 n값인 15와 같을때 count를 해주게 되면! 답이 나온다.

function solution(n) {
  let result = 0;
  let count = 0;
  while (n > 0) {
    count++;
    n = n - count;
    if (n % count == 0) result++;
  }
  return result;
}

- while문 하나로 문제를 풀 수 있다. 효율성도 통과했다.

- 다른 문제들도 이런경우로 만약에 풀어야하게 되면 더 깊은 생각을 해야할거 같다..

- 이건 어떻게 보면 이과가 아닌 나한테는.... 두배 세배 힘든 문제인거 같다..