Algorithm2[공부 : 숫자의 표현]

문제 설명

자연수 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

 

내가 처음 푼 풀이 (틀림)

Logic
1은 무조건 있고
2는 홀수면 있음
3이상부터는 나누어지면 있음
약수를 구해서
1,2 3이상의 홀수 여야함

약수와 반대편에 있는 약수 중
작은수가 큰수의 절반보다 커야함

function solution(n) {
  if (n < 3) {
    return 1;
  }

  let count;
  //1 무조건 됨 2는 홀수 면 가능
  if (n % 2 === 0) {
    count = [1];
  } else {
    count = [1, 2];
  }
  for (let i = 3; i <= Math.sqrt(n); i++) {
    // i는 약수여야 하고,
    if (n % i === 0) {
      // i는 홀수 여야 조건에 맞음
      if (i % 2 === 1) count.push(i);
      // 제곱근이 아니면 나눈수 확인하기
      if (n / i !== i) {
        // 나눈수가 홀수 이고 i가 나눈수의 절반이상이면 가능 (count++)
        if ((n / i) % 2 === 1 && n / i / 2 <= i) count.push(n / i);
      }
    }
  }

  return count.length;
}

테스트 1 〉 통과 (0.06ms, 29.8MB)
테스트 2 〉 실패 (0.06ms, 30.1MB)
테스트 3 〉 실패 (0.06ms, 29.9MB)
테스트 4 〉 실패 (0.06ms, 29.9MB)
테스트 5 〉 통과 (0.06ms, 30.1MB)
테스트 6 〉 통과 (0.05ms, 29.7MB)
테스트 7 〉 실패 (0.07ms, 29.9MB)
테스트 8 〉 실패 (0.09ms, 30MB)
테스트 9 〉 통과 (0.05ms, 29.9MB)
테스트 10 〉 통과 (0.08ms, 30MB)
테스트 11 〉 통과 (0.09ms, 30.1MB)
테스트 12 〉 실패 (0.05ms, 30.1MB)
테스트 13 〉 실패 (0.05ms, 30MB)
테스트 14 〉 통과 (0.08ms, 29.9MB)
테스트 15 〉 통과 (0.07ms, 29.9MB)
테스트 16 〉 통과 (0.05ms, 30.1MB)
테스트 17 〉 실패 (0.05ms, 30MB)
테스트 18 〉 통과 (0.05ms, 29.9MB)
효율성 테스트
테스트 1 〉 실패 (0.08ms, 29.5MB)
테스트 2 〉 실패 (0.08ms, 29.6MB)
테스트 3 〉 실패 (0.09ms, 29.6MB)
테스트 4 〉 실패 (0.08ms, 29.6MB)
테스트 5 〉 실패 (0.09ms, 29.6MB)
테스트 6 〉 실패 (0.09ms, 29.7MB)

 

틀린 이유

 - 로직이 틀렸음 

 

다시 푼 풀이

Logic
1부터 숫자들을 연속적으로다 더해서 목표값과 같은지 확인후 
같으면 갯수를 셈
목표값보다 크면 시작숫자는 전보다 1을 더함

function solution(n) {
  let count = 0;
  // 시작하는 숫자
  for (let i = 1; i <= n; i++) {
    let sum = 0;
    // i부터 시작해서 끝까지 더함
    for (let j = i; j <= n; j++) {
      sum += j;
      //목표값과 같거나 크면 종료
      if (sum >= n) {
        // 목표값과 같으면 갯수를 셈
        if (sum === n) count++;
        break;
      }
    }
  }
  return count;
}

테스트 1 〉 통과 (0.05ms, 29.7MB)
테스트 2 〉 통과 (0.14ms, 29.6MB)
테스트 3 〉 통과 (0.14ms, 30MB)
테스트 4 〉 통과 (0.18ms, 30.2MB)
테스트 5 〉 통과 (0.10ms, 30MB)
테스트 6 〉 통과 (0.09ms, 29.9MB)
테스트 7 〉 통과 (0.14ms, 30MB)
테스트 8 〉 통과 (0.08ms, 29.9MB)
테스트 9 〉 통과 (0.07ms, 30.1MB)
테스트 10 〉 통과 (0.18ms, 30.1MB)
테스트 11 〉 통과 (0.24ms, 30MB)
테스트 12 〉 통과 (0.17ms, 30.1MB)
테스트 13 〉 통과 (0.18ms, 29.8MB)
테스트 14 〉 통과 (0.18ms, 29.8MB)
테스트 15 〉 통과 (0.07ms, 30MB)
테스트 16 〉 통과 (0.07ms, 30.1MB)
테스트 17 〉 통과 (0.07ms, 29.9MB)
테스트 18 〉 통과 (0.04ms, 29.7MB)
효율성 테스트
테스트 1 〉 통과 (3.11ms, 32.4MB)
테스트 2 〉 통과 (2.11ms, 32.6MB)
테스트 3 〉 통과 (2.68ms, 32.5MB)
테스트 4 〉 통과 (1.73ms, 32.5MB)
테스트 5 〉 통과 (1.91ms, 32.4MB)
테스트 6 〉 통과 (2.16ms, 32.4MB)

 

다른 사람 풀이

function expressions(num) {
  var answer = 0;

  for (var i = 1; i <= num; i++) {
    if (num % i == 0 && i % 2 == 1) answer++;
  }
  return answer;
}

Logic
n의 약수 중에 홀수의 갯수

=>> 이게 되는 이유는 모르겠음

테스트 1 〉 통과 (0.07ms, 30.1MB)
테스트 2 〉 통과 (0.05ms, 30.1MB)
테스트 3 〉 통과 (0.05ms, 30.2MB)
테스트 4 〉 통과 (0.05ms, 30.1MB)
테스트 5 〉 통과 (0.06ms, 30MB)
테스트 6 〉 통과 (0.05ms, 29.8MB)
테스트 7 〉 통과 (0.10ms, 30.1MB)
테스트 8 〉 통과 (0.04ms, 30.1MB)
테스트 9 〉 통과 (0.04ms, 30.1MB)
테스트 10 〉 통과 (0.09ms, 30.2MB)
테스트 11 〉 통과 (0.05ms, 30MB)
테스트 12 〉 통과 (0.08ms, 29.8MB)
테스트 13 〉 통과 (0.08ms, 29.8MB)
테스트 14 〉 통과 (0.09ms, 29.8MB)
테스트 15 〉 통과 (0.04ms, 30MB)
테스트 16 〉 통과 (0.03ms, 29.9MB)
테스트 17 〉 통과 (0.05ms, 30.1MB)
테스트 18 〉 통과 (0.05ms, 30MB)
효율성 테스트
테스트 1 〉 통과 (0.42ms, 30MB)
테스트 2 〉 통과 (0.28ms, 30.1MB)
테스트 3 〉 통과 (0.32ms, 30MB)
테스트 4 〉 통과 (0.32ms, 29.7MB)
테스트 5 〉 통과 (0.38ms, 30.1MB)
테스트 6 〉 통과 (0.37ms, 29.5MB)

 

다른 사람 풀이2

function expressions(num) {
  var answer = 0;
  var k = 0;

  while ((k * (k - 1)) / 2 <= num) {
    // (num / k - (k - 1) / 2이게 정수인가?
    // =>  k의 값이 가 짝수면 - 0.5 홀수면 - 0.0해서 정수 인지 확인
    // num / k - (k - 1) / 2 != 0
    // => num / k !== (k - 1) / 2
    // => num !== k*(k-1)/2
    if (Number.isInteger(num / k - (k - 1) / 2) && num / k - (k - 1) / 2 != 0) {
      answer++;
    }
    k++;
  }

  return answer;
}

Logic
n의 갯수로 나누어서 그 숫자들이 연속적으로 이어지는 가

=> 정확히 이해하지는 못했음 나중에 한번더 봐야겠음

테스트 1 〉 통과 (0.09ms, 30.1MB)
테스트 2 〉 통과 (0.07ms, 30MB)
테스트 3 〉 통과 (0.06ms, 30.2MB)
테스트 4 〉 통과 (0.05ms, 30.1MB)
테스트 5 〉 통과 (0.05ms, 30.1MB)
테스트 6 〉 통과 (0.09ms, 30.1MB)
테스트 7 〉 통과 (0.10ms, 30MB)
테스트 8 〉 통과 (0.05ms, 30MB)
테스트 9 〉 통과 (0.07ms, 30.1MB)
테스트 10 〉 통과 (0.05ms, 30.2MB)
테스트 11 〉 통과 (0.05ms, 30.2MB)
테스트 12 〉 통과 (0.05ms, 30MB)
테스트 13 〉 통과 (0.05ms, 30.1MB)
테스트 14 〉 통과 (0.05ms, 30.1MB)
테스트 15 〉 통과 (0.04ms, 30.1MB)
테스트 16 〉 통과 (0.04ms, 30.2MB)
테스트 17 〉 통과 (0.05ms, 30.1MB)
테스트 18 〉 통과 (0.04ms, 30.1MB)
효율성 테스트
테스트 1 〉 통과 (0.07ms, 29.9MB)
테스트 2 〉 통과 (0.08ms, 29.5MB)
테스트 3 〉 통과 (0.09ms, 29.8MB)
테스트 4 〉 통과 (0.08ms, 29.9MB)
테스트 5 〉 통과 (0.07ms, 29.9MB)
테스트 6 〉 통과 (0.06ms, 30.1MB)

 

다른 사람 풀이3

처음본 문법 do... while

ref

function expressions(num) {
  var start = 0,
    way = 0;

  do {
    start++;

    var f_result = start;

    for (let i = start + 1; i <= num; i++) {
      f_result += i;

      if (f_result > num) {
        break;
      } else if (f_result == num) {
        way++;
      }
    }
  } while (start != num);

  return way + 1;
}

Logic
1부터 숫자들을 연속적으로다 더해서 목표값과 같은지 확인후 
같으면 갯수를 셈
목표값보다 크면 다시 처음부터 시작하고
시작숫자는 전보다 1을 더함
(나와같음)