[프로그래머스] 숫자 블록 (Lv 2) - javascript

문제

그렙시에는 0으로 된 도로에 숫자 블록을 설치하기로 하였습니다. 숫자 블록의 규칙은 다음과 같습니다.
 
블록의 번호가 n 일 때, 가장 처음 블록은 n * 2번째 위치에 설치합니다. 그다음은 n * 3, 그다음은 n * 4, ...로 진행합니다.만약 기존에 블록이 깔려있는 자리라면 그 블록을빼고 새로운 블록으로 집어넣습니다.
 
예를 들어 1번 블록은 2,3,4,5, ... 인 위치에 우선 설치합니다. 그다음 2번 블록은 4,6,8,10, ... 인 위치에 설치하고, 3번 블록은 6,9,12... 인 위치에 설치합니다.
 
이렇게 3번 블록까지 설치하고 나면 첫 10개의 블록은 0, 1, 1, 2, 1, 3, 1, 2, 3, 2이됩니다.
 
그렙시는 길이가 1,000,000,000인 도로에 1번 블록부터 시작하여 10,000,000번 블록까지 위의 규칙으로 모두 놓았습니다.
 
그렙시의 시장님은 특정 구간의 어떤 블록이 깔려 있는지 알고 싶습니다.
 
구간을 나타내는 두 수 begin, end 가 매개변수로 주어 질 때, 그 구간에 깔려 있는 블록의 숫자 배열(리스트)을 return하는 solution 함수를 완성해 주세요.
 

제한 사항

• begin, end 는 1 이상 1,000,000,000이하의 자연수 이고, begin는 항상 end보다 작습니다.
• end - begin 의 값은 항상 10,000을 넘지 않습니다.
   

🤔 풀이 과정

answer[n]에는 n의 약수 중 본인을 제외한 가장 큰 수가 들어가게 된다.
for문으로 2부터 순회하여 나누어 떨어지는 수를 찾은 다음, 몫을 넣어주면 된다.
이중 for문으로 구현했다가, 함수로 경우를 나눠 구현하는 과정을 거쳐 4차까지 풀이를 고쳤다.
모두 정확성은 통과했지만 효율성은 통과하지 못해서 고민하다가 문제를 다시 읽고 효율성까지 통과했다.
 
문제는 쉬운 듯 하지만, 디버깅하는 과정에서 많은 것을 배운 문제다.
 

1차 풀이

function solution(begin, end) {

    let answer = [];

    for(let i = begin; i <= end; i++) {
        if(i <= 3) answer.push([0,0,1,1][i]);
        else {
            for(let j = 2; j <= i/2; j++) {
                if(!(i % j)) {
                    answer.push(i/j);
                    break;
                }
                else if(j === Math.floor(i/2)) answer.push(1);
            }
        }
    }
    return answer;
}

 
for문 안에서 예외처리를 하려다보니 쓸데없는 순회가 발생해서 속도가 느려진다.
 

• 정확성 테스트
  

  

  
   

2차 풀이

function solution(begin, end) {

    let answer = [];

    function check(i) {
        if(i === 1) return 0;
        else {
            for(let j = 2; j <= i/2; j++) {
                if(i % j === 0) return i/j;
            }
        }
    }

    for(let i = begin; i <= end; i++) {
        if(check(i) !== undefined) answer.push(check(i));
        else answer.push(1);
    }

    return answer;
}

 
아예 함수를 따로 만들어 처리했다.
함수로 묶어서 처리하도록 제한하는 코테도 있다고 들었다.
처음부터 이렇게 문제를 푸는 것이 좋을 듯.
 

• 정확성 테스트
  

  

  
   

🔑 모범 풀이

function check(i) {

    if(i === 1) return 0;

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

    return 1;
}

function solution(begin, end) {

    let answer = [];

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

    return answer;
}

 
약수를 순회하는 부분을 수정했다.
약수를 구할 때, Math.sqrt(i)까지만 순회해도 충분하다.
그렇게 하면 n이 2일 경우의 처리를 따로 하지 않아도 되고, 효율적이다.
 

• ✔ 효율성 테스트 통과하기

  계속 효율성 통과가 안됐는데, 그 이유를 문제에서 찾을 수 있었다.
  10,000,000번 블록까지 위의 규칙으로 모두 놓았습니다. 라는 부분이다.
  그러므로 약수 중, 10,000,000 이하의 최대의 수를 구해야 한다.
  i/j <= 1e7 를 조건에 추가했더니 통과했다.
  (1e7 = 10,000,000)
   

• 정확성 테스트

  

  
   

• 효율성 테스트
  

  

  
   

---

참고

velog.io/@longroadhome