[프로그래머스/Level2] 숫자 블록 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 소수/약수 (에라토스테네스의 체)

begin부터 end까지의 범위 내에 있는 숫자들 중 해당 수의 가장 큰 약수를 블록에 적는다. 단, 블록에 적는 숫자는  10,000,000 보다 작거나 같아야 한다!

 

또, 숫자가 1인 경우만 블록에 0을 두는 예외처리가 필요하다.

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static final int MAX = 10_000_000;
    
    public List<Integer> solution(long begin, long end) {
        List<Integer> answer = new ArrayList<>();
        
        for(long i = begin ; i <= end ; i++) {
            if(i == 1) {    // 1인 경우만 예외처리
                answer.add(0);
                continue;
            }
            
            // 1이 아니면 블록에 제일 큰 약수 두기
            answer.add((int)getGCD(i));
        }
        
        return answer;
    }
    
    // 블록에 둘 제일 큰 약수 구하는 메소드
    private static long getGCD(long x) {
        long result = 1;
        
        for(long i = 2 ; i <= Math.sqrt(x) ; i++) {
            if(x % i == 0) {
                result = i;
                
                if(x/i <= MAX) {    // 블록 숫자는 MAX보다 크면 안 됨!
                    result = x/i;
                    break;
                }
            }                
        }
        
        return result;
    }
}

 

 

---

💦 어려웠던 점

- 그냥 반복문으로 갯수+1하면서 최대 약수 구할 생각을 했다.

-  10,000,000 보다 작거나 같은 수여야 한다는 조건을 놓쳤다.

- 표를 보고 dp로 풀어야하나..라는 생각을 꽤 오래 했다.

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[Programmers] Lv2. 숫자 블록 | C++

 

[프로그래머스,자바] Level2: 숫자블록