프로그래머스 LV.0 순서쌍의 개수

프로그래머스 LV.0 순서쌍의 개수

https://school.programmers.co.kr/learn/courses/30/lessons/120836

프로그래머스

 

1. 문제 명

순서쌍의 개수

2. 문제 설명

순서쌍이란 두 개의 숫자를 순서를 정하여 짝지어 나타낸 쌍으로 (a, b)로 표기합니다. 자연수 n이 매개변수로 주어질 때 두 숫자의 곱이 n인 자연수 순서쌍의 개수를 return하도록 solution 함수를 완성해주세요.

3. 제한 사항

- 1 ≤ n ≤ 1,000,000

4. 예시

n	result
20	6
100	9

5. 기본 제공 코드

function solution(n) {
    var answer = 0;
    return answer;
}

6. 제출한 내 답

const solution = (n) => {
  let count = 0;
  for (i = 1; i <= n; i++) {
    if (n % i === 0) {
      count += 1;
    }
  }
  return count;
};

 

6-2. VSC에 작성한 내용

const solution = (n) => {
  let count = 0;
  for (i = 1; i <= n; i++) {
    if (n % i === 0) {
      // let j = n / i;
      // console.log(`${i}, ${j}`);
      count += 1;
    }
  }
  return count;
};

// 힌트
// (i * j = n)은 (n / i = j)도 성립하기 때문에
// j를 1부터 n까지 찾는 대신에
// n이 i로 나누어 떨어지는지 확인하고,
// n을 i로 나눈 몫으로 j를 바로 구할 수 있다.

// 테스트
console.log(solution(20));
console.log(solution(4));
console.log(solution(25));
console.log(solution(100));
// console.log(solution());

7. 특이사항

우선 이런식으로 작성해봤음

const solution = (n) => {
  let count = 0;
  for (i = 0; i <= n; i++) {
    for (j = 0; j <= n; j++) {
      if (i * j === n) count += 1;
    }
  }
  return count;
};

수가 크면 실행시키는데 너무 오래 걸리지 않을까? 생각해봤는데

역시나

다른 방법을 찾아야 했음

 

그렇다면 n의 절반까지만 계산해보고, for(i=1; i <= Math.ceil(n/2)); j++)

count*2를 하면 어떨까? -> 이건 4처럼 (1, 4), (2, 2), (4, 1) 순서쌍이 3개인 경우도 있으니 안됨

 

아니면 안쪽 반복문의 조건을 j는 n부터, j-- 로 설정하면 어떨까?

-> 앞에서 오나 뒤에서 오나 계산 횟수는 같음

 

고민하다가 질문하기를 눌러봤는데 나와 같은 상황인 사람들이 많았고

그 중 답변 하나에서 정답을 알게되었다.

const solution = (n) => {
  let count = 0;
  for (i = 1; i <= n; i++) {
    if (n % i === 0) {
      let j = n / i;
      console.log(`${i}, ${j}`);
      count += 1;
    }
  }
  return count;
};

적혀있는대로 코드를 작성해서 테스트 해보니 순서쌍이 정확하게 나왔고...

재출해서 통과는 하긴 했는데 스스로의 힘으로 푼게 아니라 많이 아쉽다

8. 다른 사람이 작성한 답

8-1.

function solution(n) {
    let ans = 0;
    for (let i = 1; i < Math.sqrt(n); i++)
        if (n%i === 0) ans+=2;

    return Number.isInteger(Math.sqrt(n)) ? ans+1 : ans;
}

 

8-2.

function solution(n) {
    const answer = []
    for (let i = 0; i < n + 1; i++) {
        if (n % i === 0) {
            answer.push(i)
        }
    }
    return answer.length
}