프로그래머스 | LV.2 숫자 블록 - 단순 구현 문풀 (Java)

⬛ 프로그래머스 | LV.2 숫자 블록 - 단순 구현 문풀 (Java)

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

프로그래머스

문제 설명

예제 설명

---

💚문제 접근 방식

문제를 유심히 보면서 각 값에 대해서 그 약수 중 max값이 배열값으로 담긴다는 규칙성을 발견했다.

이 데이터 크기가 무슨 10억까지로 되어 있는데..  최대한 효율적으로 처리해야 하고 주의해야 한다.

아 그리고  처음에 각 블록에 적힌 숫자 값이 10,000,000까지인 것을 못봤다.   

=> 걍 0 이 많길래 10억 길이 만큼 각각의 블록 값도 들어올 수 있는 건 줄 알았는데 자세히 보니 약수 중 자기 자신 제외 최대 값을 구하더라도 그게 Limit 값을 넘지는 않도록 조절하는 로직이 추가되어야 한다.

 

1) begin과 end는 1~10억 사이의 값이기는 하나, [end-begin] 이 5000 이내일 것이라고 되어 있다.

 

2) 일단, 목표는 for문을 최대한 많이 안타는 거고, begin~end까지 순회하면서 가장 효율적인 방식으로 약수의 최대값을 구해서 리턴받아야 할 것이라 생각했다.

 

3) getValueMax() 메소드를 호출하면 내부적으로 Math.sqrt(val) 까지의 값 中

     (1) Limit < expect (즉, 문제에서 각 블록의 최대 크기를 10^7로 지정) 을 넘으면 나눈 i값 세팅

     (2) Limit > expect : 이 경우는 Limit을 넘지 않는 값이므로 val을 i로 나눈 값을 세팅

 

4) 이제 리턴받은 각 블록값으로 세팅된 answer를 최종 리턴하면 정답 처리가 되는 문제였다.

 

💚 제출 코드

class Solution {
    private static long Limit =  10000000;
    //약수 중 가장 max 반환
    public static int getValueMax(int val){
        if (val == 1) {
            return 0;
        }

        int answer = 1;

        for (int i = 2; i <= Math.sqrt(val); i++) { 
            if (val % i == 0) {
                int expect = val / i;
                if (expect > Limit) {
                    answer = i;
                } else {
                    answer = expect;
                    return answer;
                }
            }
        }

        return answer;
    }

    //솔루션 함수
    public int[] solution(long begin, long end) {
        long N = end- begin +1;

        int[] answer = new int[(int) N];
        // answer[0] = 0; // 필요없어서 삭제
        //매번 idx+1에 대해서
        for(int i= (int)begin ; i <= (int) end; i++){
            answer[i - (int)begin] = getValueMax(i); // answer 인덱스 접근 유의
        }

        return answer;
    }
}