Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.
n은 10,000 이하의 자연수 입니다.
n | result |
---|---|
15 | 4 |
입출력 예#1
문제의 예시와 같습니다.
처음에는 1부터 시작점을 정해서 계속 더하기를 시전하려고 했다.
하지만 시간초과가 발생하였고 테스트도 통과하지 못했다.
아래의 코드가 바로 그 코드다.
// 틀린 코드
function solution(n) {
let res = 1;
for (let i = 1; i < n / 2 + 1; i++) {
let sum = 0;
let plus = i;
while (sum <= n) {
sum += plus;
plus += 1;
if (sum === n) {
res += 1;
break;
}
}
}
return res;
}
시간초과를 해결하고 내가 고려하지 못한 부분을 해결한 코드는 아래와 같다.
// 통과한 코드
function solution(n) {
let res = 1; // 자기자신
// 내림차순으로 더하기 (오름차순으로 했을 때 시간초과 발생)
for (let i = parseInt(n / 2) + 1; i > 1; i--) {
let sum = i;
for (let j = i - 1; j > 0; j--) {
sum += j; // 연속해서 수 더하기
if (sum > n) break; // n보다 수의 합이 크면 break
// 연속한 자연수의 합이 n인 경우
if (sum === n) {
res += 1;
break;
}
}
}
return res;
}
break
를 사용했고, for
문의 i
의 초기값을 parseInt(n / 2) + 1
로 잡아서 이전 코드와 달리 내림차순으로 숫자를 더하도록 수정하였다.
function expressions(num) {
var answer = 0;
for (var i = 1; i <= num; i++) {
if ((num % i == 0) && (i % 2 == 1)) {
answer++;
}
}
return answer;
}
사실 나도 처음 코드를 갈아엎을 때 홀수의 경우에 약수의 개수와 연관이 있다는 것을 알게 되었다. 하지만 코드를 작성해서 제출했더니 틀린 케이스가 더 많아져서 다른 방식으로 이 문제를 풀었다. 알고리즘을 풀 때 규칙을 잘 파악하는 것도 중요한 것 같다.