[Javascript] 숫자 블록 (12923)

문제링크

코딩테스트 연습 - 숫자 블록

 

접근 방법

처음엔 간단하게 2중 for문을 사용하여 1 ~ end까지의 result array를 구하여 
begin부터 end까지 slice하여 답을 구하였다.

그런데 주어진 begin과 end의 범위가 1 ~ 1천만으로 넒은 범위를 가지고 있어 2중 for문으로 사용하면 O(n^2)으로 

이렇게 긴 시간이 걸렸다.

그래서 최대 nlogn의 시간복잡도를 갖도록 풀이를 다시 생각하였다.
고칠점 1. 1부터 end까지 모두 구하는게 너무 비효율적인거 같다

고칠점 2. 문제를 다시 보면 약수가 존재한다면 약수의 최대 값을 갖고, 약수가 존재하지 않으면 1을 갖는다는 규칙이 있다.

이를 활용하여 begin부터 end까지 소수이면 1, 소수가 아니면 최대 약수를 갖도록 풀이를 진행하였다.

그 결과 정확성 테스트에서 시간복잡도 효율은 매우 증가했는데, 여전히 효율성 테스트에서 탈락하였다.

최대 약수를 더 효율적으로 구하는 방법이 있나? 
begin부터 end범위 내에 소수일때 1을 넣는 것 까지는 효율성에 문제가 있어보이진 않았다.
소수가 아닐 때 최대 약수를 구하는 방식을 고쳐야할 것 같은데
방법이 잘 생각이 안나서 다른 분의 코드를 참고하였다.

const getDivisor = (num) => {
  for(let i = 2; i <= Math.sqrt(num); i++) {
    if(num % i === 0 && num / i <= 1e7) {
      return num / i;
    }
  }
  return 1;
}​

 

예상대로 내가 구했던 소수 판단 함수와 최대 약수를 구하는 함수를 하나로 합쳐 구현하셨다.

begin과 end의 범위가 1 ~ 1,000,000,000 이지만 블록의 수는 최대 10,000,000개이므로
매개변수 num(begin)이 i로 나눈 값 (블록에 넣을 값)이 10,000,000보다 크다면 1을 return하도록 해야 효율성 테스트를 통과할 수 있다.

 

function solution(begin, end) {
    const resultArr = new Array((end - begin)+1).fill(0);
    let resultIdx = 0;
    while(begin <= end){
        if (begin === 1) {
            resultArr[resultIdx] = 0;
            resultIdx++;
            begin++;
            // console.log("1일때", resultArr, "begin", begin);
        }

        // 소수일때, 아닐때 처리
        getDivisor(begin) === 1 ? resultArr[resultIdx] = 1 : resultArr[resultIdx] = getDivisor(begin)
        resultIdx++;
        begin++;
            
    }

    return resultArr
}

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

 

// 시간복잡도 효율성 증가, 여전히 효율성 테스트 탈락
// 주어진 범위(begin, end) 내의 조건에 맞는(소수일때 1, 아닐때 최대 약수) 경우만 resultArr에 넣는 경우

function solution(begin, end) {
    const resultArr = new Array((end - begin)+1).fill(0);
    let resultIdx = 0;
    while(begin <= end){
        if (begin === 1) {
            resultArr[resultIdx] = 0;
            resultIdx++;
            begin++;
            // console.log("1일때", resultArr, "begin", begin);
        }

        isPrime(begin) ? resultArr[resultIdx] = 1 : resultArr[resultIdx] = findMaxDivided(begin);
        resultIdx++;
        begin++;
    }

    return resultArr
}


const findMaxDivided = (num) => {
    let max = 0;
    for(let i = 2; i <= Math.floor(num / 2); i++){
        if(num % i === 0) max = Math.max(max, i);
    }
    return max;
}

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

// 정확성, 효율성 모두 탈락한 코드
// 1~end까지 모든 경우를 구하고 원하는 부분(begin, end)만 추출한 코드

function solution(begin, end) {
    const resultArr = new Array(end).fill(0);
    
    for(let i = 1; i <= Math.floor(end / 2); i++){
        for(let j = 0; j <= end; j++){
            if(j % i === 0 && i !== j){
                resultArr[j] = i
            }
        }
    }

    return resultArr.slice(begin, end+1)
}