[프로그래머스] Lv2 숫자 블록 (Java)

프로그래머스

 

문제 설명

숫자 0이 적힌 블록들이 설치된 도로에 다른 숫자가 적힌 블록들을 설치하기로 했습니다. 

숫자블록을 설치하는 규칙은 다음과 같습니다.

블록에 적힌 번호가 n일 때, 가장 첫 블록은 n*2번째 위에 설치합니다. 그다음은 n*3, n*4,.. 위에 설치합니다.

기존에 설치된 블록은 빼고 새로운 블록을 집어넣습니다.

 

블록이 1이 적힌 블록부터 숫자를 1씩 증가시키며 순서대로 설치하면 2, 3, 4, 5, ....

그다음은 2가 적힌 블록은 4, 6, 8, 10,... 인 위치에 설치하고,

3이 적힌 블록은 6, 9, 12,... 인 위치에 설치합니다.

 

길이가 1,000,000,000인 도로에 1부터 10,000,000까지의 숫자가 적힌 블록들을 이용해 위의 규칙대로 설치했습니다.

특정 구간에 어떤 블록이 깔려 있는지 알고 싶습니다.

구간을 나타내는 두 정수 begin, end가 매개변수로 주어질 때, 구간에 깔려 있는 블록의 숫자 배열을 return 해주세요.

 

깔리는 순서 예시)

 

제한사항

• 1 ≤ begin ≤ end ≤ 1,000,000,000
• end - begin ≤ 5000

---

-Focus On-

• 설치되는 블록은 1 ≤ block ≤ 10,000,000까지의 범위에 유의해야 합니다.
• 어떤 위치에 0이 아닌 블록이 깔려 있다면 그 블록의 숫자는 현재 위치의 약수입니다.
• 약수를 구할 때, 1부터 n(현재 위치)까지 모든 경우의 약수를 찾는다면 → 시간 초과
  따라서 약수를 구할 범위를 잘 지정해야 합니다!!

 

풀이 과정

1. 위치 n에 놓일 블록은 어떤 블록인가?

현재 n번의 위치에 최종적으로 놓아질 블록을 구한다고 합시다.

n=16이라고 하면 다음과 같은 과정을 거쳐 블록 8이 마지막에 남아있는 걸 확인할 수 있습니다.

n번 자리에 들어오는 블록은 모두 (자기 자신을 제외한) 16의 약수라는 걸 확인할 수 있고,

따라서 마지막에 n번 자리 블록은 (자기자신을 제외한) n의 약수 중에  가장 큰 수라고 할 수 있습니다.

 

2. 약수를 1부터 n-1까지 맞는지 일일이 확인하면 시간초과 나는데?

n번자리의 블록을 구할 때 다음과 같이 구하면 시간초과가 나게 됩니다.

int answer=0;
for(int i=1;i<n;i++){//1부터 n-1까지 
    if(n%i==0) answer=i; //n이 i로 나눠떨어진다면 block i로 바꿔줌.
}
return answer;

따라서 시간복잡도 O(n)으로는 안됩니다.

 

이걸 줄이려면 i<n의 범위를 변경해줘야 합니다.

16의 약수는 다음과 같은데요.

√16 = 4를 기준으로 (1*16), (2*8), (4*4) 짝이 지어집니다.

따라서 n-1까지 모두 확인하는 것이 아니라 √n까지만 확인하면 그 안의 약수를 모두 구할 수 있다는 것이 됩니다.

 

이걸 적용해서 n자리의 블록을 구해보면 다음과 같습니다.

int answer=0;//n자리의 블록
for(int i=1;i*i<=n;i++){ //i는 1부터 √n까지 1씩 늘립니다
    if(n%i==0){ //i가 j로 나눠떨어질 때
    	if(n/i!=n){ //i/j가 자기자신(n)이 아니라면
        	answer = i/j;break; // 블록을 i/j로 넣어줍니다.
            	//여기서 break를 거는 이유는 약수의 최댓값은 (i가 작을 때의 그 짝)이기 때문입니다. 
        }else if(j!=n){// i/j를 구할 수 없다면 
        	answer = j; //j라도 넣어주고 더 큰 약수를 계속 찾습니다.
        }
    }
}
return answer;

 

이걸 활용해서 전체 코드를 짰습니다. 각 주석을 통해서 더 자세하게 설명을 적어두었습니다.

---

class Solution {
    public int[] solution(long begin, long end) {
        int[] answer = new int[(int)(end-begin+1)]; // begin~end까지 공간 만들어줌.
        
        int index=0;//answer 인덱스 번호
        for(long i=begin;i<=end;i++){ // i에서 begin~end까지의 자리를 하나씩 계산합니다.
                            //begin과 end가 long형으로 들어왔으므로 i도 long형으로 선언.
            for(int j=1;j*j<=i;j++){ //약수를 구할 범위를 i의 제곱근까지만.
                if(i%j==0){ //i가 j로 나눠떨어질 때
                
                    //기본적으로 i/j가 i보다 크기 때문에 i/j가 최종 블록이 되지만,
                    //조건에 블럭 범위가 10,000,000을 넘으면 안되고 자기자신이면 안된다는 조건에 의해
                    //else로 넘어가는 경우가 있습니다.
                    //그럴 때는 j보다 더 큰 값이 있을 수도 있기 때문에 break를 하지 않고
                    //다음 i/j를 더 구해봅니다.
                    
                    
                    if(i/j<=10000000 && i/j!=i){ // i/j가 블록 범위를 벗어나지 않고, 자기자신이 아니면
                        answer[index]=(int)(i/j);break;  //int형으로 바꿔 answer에 넣어주고, break -> 이게 약수 중에 가장 큰 수 
                    }else if(j!=i){ // i/j 블록을 사용할 수 없다면
                        answer[index]=j; //자기자신이 아닌 j를 넣고 더 조사합니다.
                    }
                }
            }
            index++;//다음 자리
        }
        
        
        return answer;
    }
}