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

문제 링크

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️⃣ 제한 사항

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

---

3️⃣ 입출력 예

4️⃣ 나의 풀이

1차 풀이

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이 주어진 수(n)보다 작으면 now에 1을 더한 후 넘어간다.
• 크거나 같으면 plusNum초기화
• 첫 번째 수인 count 업그레이드, now에 count를 대입하는 과정을 실행, plusNum이 n보다 클 때 answer+1

결과

효율성 테스트 시관 초과로 실패

---

2차 풀이

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와 같다.
약수의 규칙을 찾아내 풀이에 적용하니 훨씬 빠른 속도로 실행 가능하다.