[프로그래머스 Level.2] 숫자 블록 (연습문제) (Java)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12923

프로그래머스

 

 

 

 

코딩테스트 연습 > 연습문제 > 숫자 블록

 

 

 

문제 설명

 

 

그렙시에는 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

다음과 같이 블럭이 깔리게 됩니다.

 

 

 

 

 

 

 

나의 코드

class Solution {
    public int[] solution(long begin, long end) {
        int[] answer = new int[(int) end - (int) begin + 1];
        
        for(int i=(int) begin; i<=(int) end; i++) {
            answer[i - (int) begin] = getBlockNumber(i);
        }
        
        if((int) begin == 1) answer[0] = 0;
        
        return answer;
    }
    
    public int getBlockNumber(int i) {
        for(int j=2; j<=Math.sqrt(i); j++) {
            if(i % j == 0 && i/j <= 10000000) return i/j;
        }
        
        return 1;
    }
}

 

풀이

1. begin ~ end까지의 블록을 구하는 것이기 때문에 answer의 크기는 end - begin + 1이 된다.
   begin과 end가 long형으로 주어졌고  1000000000 이하의 자연수이기 때문에 문제없이 int로 캐스팅 하여 사용하도록 한다.
2. 그리고 begin부터 end까지 for문을 돌면서 블록의 번호를 구해 answer의 0인덱스(begin부터 시작이므로 i - begin)부터 순서대로 저장해준다.
3. 번호가 n일 때 2*n, 3*n, 4*n .... 번 째 블록에 번호를 저장하기 때문에 블록의 번호를 구하는 방법은 약수를 이용해서 구할 수 있다.
4. 해당 번호의 블록을 2부터 루트 해당 번호까지 for문을 돌린다. 2부터 시작해서 해당 번호를 나눈 나머지가 0이 되면 약수이므로 2부터 하여 제일 작은 약수를 구하고 이 약수로 해당 번호를 나눠주면 해당 번호를 제외한 제일 큰 약수를 구할 수 있다. (예를 들어 16번 째 블록을 구한다면 16이 제일 큰 약수이겠지만 2*n부터 저장하므로 8이 저장되어 있을 것이다. 그러므로 가장 작은 약수 2를 구해 16 / 2 = 8을 구한 것이다.) 
5. 나누어 떨어지는 수가 없다면 제일 첫 블록을 제외하고는 전부 1로 저장되어 있을 것이다. 
6. 다만 문제에 주어진대로 10,000,000번 블록까지만 규칙을 적용했다고 하였으므로 그 이후의 블록들은 0이 저장되어 있다. (2*n 블록부터 n으로 저장하므로 2번 째 블록부터 1로 저장하므로 첫 번째 블록은 0이다.)
7. 이렇게 구한 블록의 번호를 answer에 저장하고 좀 전에 얘기했듯이 begin이 1이라면 첫 블록은 0이므로 answer[0]을 0으로 변경하고 리턴하도록 한다.