[Programmers] 숫자 블록 - JavaScript

Joosi_Cool·2023년 5월 10일

2단계 JavaScript programmers 숫자 블록

Programmers

목록 보기

86/98

문제설명

그렙시에는 숫자 0이 적힌 블록들이 설치된 도로에 다른 숫자가 적힌 블록들을 설치하기로 하였습니다. 숫자 블록을 설치하는 규칙은 다음과 같습니다.

블록에 적힌 번호가 n 일 때, 가장 첫 블록은 n * 2번째 위치에 설치합니다. 그 다음은 n * 3, 그 다음은 n * 4, ...위치에 설치합니다. 기존에 설치된 블록은 빼고 새로운 블록을 집어넣습니다.

블록은 1이 적힌 블록부터 숫자를 1씩 증가시키며 순서대로 설치합니다. 예를 들어 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 함수를 완성해 주세요.

제한 사항

1 ≤ begin ≤ end ≤ 1,000,000,000
end - begin ≤ 5,000

입출력 예

begin	end	result
1	10	[0, 1, 1, 2, 1, 3, 1, 4, 3, 5]

입출력 예 설명

입출력 예 #1
다음과 같이 블럭이 깔리게 됩니다.
Imgur

※ 공지 - 2019년 4월 07일 테스트케이스가 변경되었습니다.
※ 공지 - 2023년 2월 09일 지문과 테스트 케이스가 수정되었습니다. 기존에 통과되었던 코드가 통과되지 않을 수 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

설계 과정

아래 함수를 만든다. -> 인자 num -> 최대 약수 중에서 자기를 뺀 최대 약수를 구하는 함수
1. num==1 이면 1은 두번째로 큰 약수가 없으므로 0을 리턴
2. 나머지는 약수를 구해서 자신을 제외한 큰 수를 구하면 된다.
-> 단 여기서 문제 조건에 10^7을 넘지 않아야 한다고 했기 떄문에 이는 패스
또한 거기서 쓰인 i를 딴 배열에 넣어둔다.
3. 만약 for문에서 리턴하지 못하고 끝까지 간다면 전에 넣어둔 배열을 확인
-> 배열에 값이 없다면 10^7을 넘는 약수가 없었던 것 -> 패스
-> 값이 있다면 거기서 제일 큰 값을 리턴
이유: 5 * 10^9의 경우 10^9는 약수로 포함하지 않고 5를 약수로 생각해야되기 때문에 이를 배열에 넣어두고, 거기서 가장 큰 값을 뽑아낸다.
4. 위에 모두 해당되지 않으면 1을 리턴 -> 소수

위의 함수를 만들었다면 start부터 end까지의 값을 순환하면서 함수에 인자로 넣고 리턴 값을 answer에 차례로 넣어준다.

정답 코드

function solution(begin, end) {
    var answer = [];
    
    // num을 넣으면 약수중에서 자신을 빼고 가장 큰 수를 리턴
    function check(num){       
        var checkArr=[];        
        if(num===1){
            return 0;
        }
        // 약수 구하기
        for(var i =2;i<=Math.sqrt(num);i++){
            if(num%i===0){
                checkArr.push(i);
                if(num/i <= 1e7){
                    return num/i;
                }
            }
        }
        if(checkArr.length!==0){
            return checkArr[checkArr.length-1];
        }     
        // 없다면 1을 리턴 (1은 모두 나눠짐.)
        return 1;
    }
    
    
    for(var i = begin;i<=end;i++){
        var checkNum = check(i);
        if(checkNum!==undefined){
             answer.push(checkNum);
        }
    }
    
    return answer;
}