프로그래머스 - 숫자 블록

leehyunjon·2022년 12월 3일
0

Algorithm

목록 보기
139/162

숫자 블록 : https://school.programmers.co.kr/learn/courses/30/lessons/12923#


Problem


Solve

도로에서 begin부터 end까지 설치된 블록을 반환하는 문제입니다.

  • 조건
    • 도로의 총 길이는 최대 10억
    • end-begin의 길이는 최대 1만
    • 사용가능한 블럭의 개수는 1천만

begin부터 end까지의 블록을 선택하기 위해서는 i번째 구간의 최대 크기의 약수가 i번째 구간의 블록이됩니다.

10번째 구간의 경우 10/2 = 5이기 때문에 5번 블록이 10번째 구간의 블록이 되게됩니다.
그렇기 때문에 i를 2부터 i번째 구간 중 나누어 떨어지는 결과가 가장 큰 블록을 반환하게 됩니다.
하지만 2부터 i번째까지의 모두 구하는 것은 비효율적입니다.
10번째 구간에서 2로 나누었을때 5번 블록이 반환됩니다. 그런데 5로 나누었을 경우에는 2번 블록이 반환되므로 2로 나누나 5로 나누나 결국 나누어 떨어지는 것은 동일한 결과가 반환되게 됩니다. 결국 O(구해야할 구간 * 2부터 i번째 구간까지 반복)의 시간복잡도로 시간초과가 발생하게 됩니다. 그렇기 때문에 i번째까지 하나씩 나누어 떨어지는지 확인하지 않고 해당 구간의 제곱근까지 나누어 떨어지는지 확인하여 O(N)에서 O(logN)으로 시간을 단축시켜줄 수 있습니다.

int block = 1;

for(int i=2;i<=Math.sqrt(number);i++){
	if(number%i == 0){
    	block = number/i;
        break;
    }
}

하지만 효율성테스트에서 시간초과가 아닌, 실패가 발생하여 갈피를 잡지 못하였습니다.
놓치고 있던 부분은 사용가능한 블록은 1부터 10000000번 블록까지 사용가능한것입니다.

도로의 길이는 최대 10억인데 2로 나누었을때 5억번째 블록을 사용할수 있게 됩니다. 하지만 사용가능한 블록은 최대 10000000번 블록까지이므로 해당 구간의 사용가능한 블록을 찾는 곳에서 조건을 추가해주면 됩니다.

int block = 1;

for(int i=2;i<=Math.sqrt(number);i++){
	//사용가능한 블록 조건 추가
	if(number%i == 0 && number/i<=10000000){
    	block = number/i;
        break;
    }
}

Code

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

Result


Reference

https://school.programmers.co.kr/questions/33585

profile
내 꿈은 좋은 개발자

0개의 댓글