Lv 2. 숫자블록

 

https://school.programmers.co.kr/learn/courses/30/lessons/12923?language=java

프로그래머스

 

 

 

자연수 n에 대해, 1과 n을 제외한 약수 중에서 10,000,000 이하인 값 중 가장 큰 값을 찾아야 한다.
만약 그런 값이 없다면 1을 반환해야 한다. 단, n이 1이라면 0을 반환합니다.

처음 작성했던 코드에서는 n의 약수를 찾을 때 첫 번째로 발견되는 약수 쌍을 이용하여

바로 반환하는 방식이었다.

하지만 이 방식은 모든 경우를 정확하게 처리하지 못했다.

 

예를 들어, n = 20000010일 때, 약수는 [1, 2, 10000005, 20000010]가된다.

이 경우 10000005는 10,000,000을 초과하므로 사용할 수 없고, 2를 반환해야 한다.

하지만 기존 코드에서는 10000005가 너무 커서 그냥 넘어가버리고,

다른 후보를 저장하지 않아서 잘못된 값을 반환하게 되었다.

 

이를 해결하기 위해, 첫 번째로 발견되는 약수 쌍만 확인하는 것이 아니라,

작은 약수도 저장해서 조건에 맞는 값을 최종적으로 선택하는 방식으로 수정했습니다.
즉, 큰 약수가 조건을 만족하면 바로 반환하고,

그렇지 않다면 작은 약수를 저장해두었다가 끝까지 적절한 값이 없을 경우

작은 약수를 반환하도록 변경했다.

문제 해결 과정에서 첫 번째로 발견된 약수만을 사용하는 것이 아니라,

적절한 후보를 저장하면서 최종적으로 가장 적합한 값을

반환하는 방식을 적용하는 것이 핵심이었다.

 

 

package Programmers;

class p_number_Block {
	private int isPrime(int n){
		if(n == 1) return 0;
		int max = 1;

		for(int i = 2 ; i <= Math.sqrt(n) ; i++){
			if(n % i == 0){
				if(n / i <= 10000000) return n / i;
				max = i;
			}
		}
		return max;
	}

	public int[] solution(long begin, long end) {
		int[] result = new int[(int)(end - begin + 1)];
		int index = 0;

		for(long i = begin ; i <= end ; i++){
			result[index++] = isPrime((int)i);
		}

		return result;
	}
}