(Java) 프로그래머스 - 숫자 블록

간단한 문제처럼 보였지만 그렇게 쉽지는 않았다.

이중 for문으로 배열을 조작하면서 풀어보았는데

begin 값이 1일때는 정상적으로 답이 나오지만

1이 아닐경우에는 답이 정상적으로 나오지 않았다.

이런 저런 시도끝에 성공하지 못해서 검색을 통해 힌트를 얻었다.

 

begin 부터 end 까지 각 블록이 먼저 소수인지 판별하여

소수라면 배열 idx에 1을 삽입하고

소수가 아니라면 가장 큰 약수를 삽입한다.

블록의 최대 개수가 10000000 이므로

약수가 10000000 이하 조건을 넣지 않으면 효율성 테스트에서 걸리게 된다.

 

---

실패 코드

class Solution {
    public int[] solution(long begin, long end) {
        int beginInt = (int) begin;
        int endInt = (int) end;
        int[] answer = new int[(endInt - beginInt + 1)];
        int idx = 0;
        
        for (int i = 1; i * 2 <= end; i++) {
            for (int j = 2; i * j <= end - begin + 1; j++) {
                answer[(i * j - 1)] = i;
            }
        }

        return answer;
    }
}

 

최종 코드

class Solution {
    public int[] solution(long begin, long end) {
        int beginInt = (int) begin;
        int endInt = (int) end;
        int[] answer = new int[(endInt - beginInt + 1)];
        int idx = 0;

        for (int i = beginInt; i <= endInt; i++) {
            // 소수 판별을 위한 변수
            boolean flag = false;

            // i가 1이면 지나감
            if(i == 1) {
                answer[idx++] = 0;
                continue;
            }

            // 에라토테네스의 채로 소수인지 판별
            for (int j = 2; j * j <= i; j++) {
                // 소수가 아니고 약수가 10000000 이하라면
                if (i % j == 0 && i / j <= 10000000) {
                    // 가장 큰 약수 삽입
                    answer[idx++] = i / j;
                    flag = true;
                    break;
                }
            }

            // 소수라면 1 삽입
            if(!flag) {
                answer[idx++] = 1;
            }
        }

        return answer;
    }
}