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

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

 

Programmers(프로그래머스)의 코딩테스트 연습문제 Level 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을 넘지 않습니다.

 

입출력 예

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

 

입출력 예 설명

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

출처 : 프로그래머스 코딩테스트 연습문제 숫자 블록

 

작성한 답

solution.js

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;
    });
}

 

설명

문제 설명과 입출력 예를 잘 이해하면 각 블록에 놓인 숫자는 해당 블록 번호의 약수 중 가장 큰 수인 것을 알 수 있습니다.

그러므로 Array.from()을 사용하여 end + 1 - begin 으로 구하려는 배열의 길이를 선언하면서,

바로 내부에서 해당 블록 번호의 최대 약수를 구하여 삽입하면서 배열을 생성하고,

해당 배열을 반환하는 것으로 문제를 해결할 수 있습니다.

 

※ "1번 블록부터 시작하여 10,000,000번 블록까지 위의 규칙으로 모두 놓았습니다." 라는 규칙에 의해,

blockNum / j <= 1e7 조건을 넣어두긴 하였지만 (해당 규칙을 넣지 않으면 효율성 테스트에서 '시간 초과'도 아닌 '실패'를 하게 됩니다.)

정확히 어떠한 이유에서 이러한 설정이 필요한 것인지는 아직 정확히는 이해하지 못했습니다.

추후에 조금 더 공부한 뒤 해당 부분 조금 더 자세히 작성해볼 수 있도록 하겠습니다.

 

 

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청사항은 언제든지 말씀해주세요!

피드백도 언제나 환영입니다!

 

감사합니다.