Problem Solving/Programmers

<Level 2> 숫자의 표현 with JS

harry_yoon 2021. 8. 16. 11:32

문제 설명

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 이하의 자연수 입니다.

 

function solution(n) {
  var answer = 0;
  let right = 1;
  let sum = 1;
  for (let left = 1; left <= n; left++) {
    while (sum < n) {
      right++;
      sum += right;
    }
    if (sum === n) answer += 1;
    sum -= left;
  }
  return answer;
}

 

- 하나하나 더해가며 확인하면 시간초과가 발생하는 문제로 보인다. 채점시 효율성을 체크하는 것으로 보아 10000이라는 제한사항은 괜히 주어진 것이 아닐 것이다.

 

- 필자는 투포인터로 해결하였다. left와 right라는 포인터를 사용하여 right가 커져가며 sum에 더해나갔다. 만약 sum이 n보다 크거나 작아지면 n과 같아졌는지 체크한다.

 

- left를 1 늘리고 left의 숫자는 sum에서 빼주고 위의 과정을 반복한다.

 

- 다른사람의 풀이를 보고 n이 가진 홀수약수의 갯수가 연속된 숫자의 합으로 표현되는 경우의 수와 같다는 것을 알게되었다. 기억해두면 쓸 곳이 있을 것 같아서 여기에 메모해둔다.

 

 


 

참고

 

 

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

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할

programmers.co.kr