프로그래머스 코딩테스트 연습 Level 2 - 숫자의 표현 (JavaScript)

프로그래머스 코딩테스트 연습 Level 2 - 숫자의 표현 (JavaScript)

 

Programmers(프로그래머스)의 코딩테스트 연습문제 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 이하의 자연수 입니다.

 

입출력 예

n	result
15	4

 

입출력 예 설명

입출력 예#1
문제의 예시와 같습니다.

 

작성한 답

solution.js

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

 

설명

먼저 정확성 테스트에서는 통과했으나 효율성 테스트에서 시간초과가 나온 방법부터 설명 해드리겠습니다.

function solution(n) {
  let answer = 1;
  for (let i = 1; i < n; i++) {
      let tmp = 0;
      for (let j = i; j < n; j++) {
          tmp += j;
          if (tmp >= n) {
              if (tmp === n) answer++;
              break;
          }
      }
  }
  return answer;
}

처음에는 2개의 중첩 반복문을 사용하여,

1부터 차례대로 연속된 수를 더하면서 자연수 n을 만들어내는 상황이 나올 때마다 가능한 방법의 수를 증가시키는 방법으로 문제를 해결했습니다.

하지만 위 방법은 말씀드렸듯 답은 정확하게 얻을 수 있지만 효율성 테스트에서는 합격하지 못했습니다.

 

그래서 해결할 수 있었던 방법을 설명해드리자면,

코드도 상당히 간결해졌는데요. 

"주어진 자연수를 연속되는 자연수들의 합으로 표현할 수 있는 방법의 수는 주어진 자연수의 약수 중에서 홀수인 수의 개수와 같다."

라는 공식을 사용하여 해결할 수 있습니다.

 

그리하여 주어진 수 n 까지 반복문을 돌며 n의 약수 이면서 홀수일 때 방법의 수를 증가시키는 방법으로 방법의 수를 구하고,

구해진 방법의 수를 반환하는 방법으로 문제를 해결할 수 있습니다.

 

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청사항은 언제든지 말씀해주세요!

피드백도 언제나 환영입니다!

 

감사합니다.