[프로그래머스 lev2/JS] 숫자 블록

문제 출처

프로그래머스 lev2 - 숫자 블록

나의 풀이

1차시도(70/100)

각 배열에는 약수 중 최대값이 들어가면 된다.

하지만 아래 풀이는 효율성을 통과하지 못 한다.

function solution(begin, end) {
  let answer = []

  for(let i=begin; i<=end; i++) {
    let cnt = 2

    if(i===1) {
      answer.push(0)
      continue
    }

    while(1) {
      if(i%cnt === 0) break
      cnt++
    }
    answer.push(i/cnt)
  }
  
  return answer
}

console.log(solution(1, 10)) // [0, 1, 1, 2, 1, 3, 1, 4, 3, 5]

다른 풀이

각 배열에는 약수 중 최대값이 들어가면 된다.

우리는 소수를 판별할 때 아래와 같이 판별하곤 한다. 제곱근까지만 for문을 순회하면서 하나라도 나눠진다면 소수가 아니므로 false를 반환하는 것이다.

function isPrime(num) {
  if(num === 1) return false
  if(num === 2) return true
  
  for(let i=2; i<=Math.sqrt(num); i++){
    if(num % i === 0) return false
  }
  return true
}

이번 문제의 풀이에서도 마찬가지 원리를 사용한다.

만약 나눠떨어진다면 그 지점에서는 소수가 아니므로 num/k를 반환하고
for문을 전부 돌았는데도 return 되지 않았다면 소수이므로 1을 반환해야 한다.

문제의 조건을 제대로 이해해야 한다.

문제에서는 1번~10_000_000번까지만 해당 규칙을 적용한다고 되어 있으므로, 이후에는 해당 규칙이 적용되지 않아야 한다.
(근데 사실 10_000_000번까지만 규칙을 적용한다고 하면 이후에는 1인 경우도 없어야 하는데, 테스트케이스 자체가 소수가 포함된 범위만 추가되어 있는 것 같기도 하다)

어쨌든 num/k <= 1e7이라는 조건을 반드시 걸어야 한다.

const findNum = (num) => {
  if(num === 1) return 0

  for(let k=2; k<=Math.sqrt(num); k++){
    if(num%k === 0 && num/k <= 1e7){
      return num / k
    }
  }
  return 1
}

function solution(begin, end) {
  let answer = []

  for(let i=begin; i<=end; i++){
    answer.push(findNum(i))
  }
  return answer
}

다른 풀이 2

function solution(begin, end) {
  return Array.from({length: end + 1 - begin}, (_, i) => {
      const blockNum = i + begin;
      if(blockNum === 1) return 0;
      for (let j = 2; j <= Math.sqrt(blockNum); j++) {
          if (blockNum % j === 0 && blockNum / j <= 1e7) {
              return blockNum / j;
          }
      }
      return 1;
  });
}

참고

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