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

프로그래머스 코딩테스트 Lv.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를 완성해주세요.

조건

1. n은 10,000 이하의 자연수 입니다.

풀이

function solution(n) {
  let answer = 0;
  let now = 1, count = 1, plusNum = 0;

  while(count <= n) {
    plusNum = plusNum + now;
    if(plusNum >= n) {
      if(plusNum === n) answer++;
      plusNum = 0;
      count++;
      now = count;
    } else {
      now++;
    }
  }

  return answer;
}

// test
console.log(solution(15)); // 4

문제에 주어진 예제 그대로 풀이에 접근했다.
지금 생각해보면 이러한 접근방법이 실행속도를 줄이지 못하는 큰 원이이 되었다.
약수를 이용하면 더 효율적이라는 것을 전혀 생각하지 못하고 짠 코드였다.

now = 현재 더하고 있는 수
count = 현재 더하고 있는 식의 가장 첫 번째 수
plusNum = 현재 더해진 결과값

plusNum에 now를 더해주며 while문을 실행했다. 만약 plusNum이 주어진 수 n보다 작으면 now에 1을 더한 후 넘어간다. 크거나 같다면 plusNum 초기화, 첫 번째 수인 count 업그레이드, now에 count를 대입하는 과정을 실행하도록 했고, plusNum이 n보다 클 때만 answer에 1을 추가해주었다.

결과

• 정확성 테스트 / 효율성 테스트를 모두 통과했으나, 실행속도가 다른 풀이에 비해 빠르지 않았다.
• 보다 빠르게 실행할 수 있는 다른 접근방법을 찾아보도록 하자.

다른 풀이

function solution(n) {
  let answer = 0;
  
  for(let i = 0; i <= n; i++) {
  	if(n%i === 0 && i%2 === 1) answer++;
  }
  
  return answer;
}

// test
console.log(solution(15)); // 4

해당 풀이는 "주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수와
주어진 수의 홀수인 약수 갯수는 같다." 는 공식을 이용한 풀이라고 한다.

• 15의 약수는 1, 3, 5, 15 이고 이 중 홀수는 4개이다.

1. 약수 1 => 연속하는 1개 자연수의 합으로 표현 가능
   15 = 15
2. 약수 3 => 연속하는 3개 자연수의 합으로 표현 가능
   15를 3으로 나눈값인 5로 표현할 수 있다.
   5 + 5 + 5 = 15 => 3 + 4 + 5 = 15
3. 약수 5 => 연속하는 5개 자연수의 합으로 표현 가능
   15를 5로 나눈값인 3으로 표현할 수 있다.
   3 + 3 + 3 + 3 + 3 = 15 => 1 + 2 + 3 + 4 + 5 = 15
4. 약수 15 => 모든 홀수(2n+1)는 n과 n+1로 표현 가능
   7 + 8 = 15

결과

• 15를 연속된 자연수의 합으로 표현하는 방법의 수는
  15의 홀수인 약수의 갯수 4와 같다.
• 약수의 규칙을 찾아내 풀이에 적용하니 훨씬 빠른 속도로 실행 가능하다.

2021.07.29