[프로그래머스 level2] 숫자 블록 - Java

<목차>

1. 문제
2. 접근 방법
3. 풀이 소스

 

[문제]

그렙시에는 숫자 0이 적힌 블록들이 설치된 도로에 다른 숫자가 적힌 블록들을 설치하기로 하였습니다. 숫자 블록을 설치하는 규칙은 다음과 같습니다.

블록에 적힌 번호가 n 일 때, 가장 첫 블록은 n * 2번째 위치에 설치합니다. 그 다음은 n * 3, 그 다음은 n * 4, ...위치에 설치합니다. 기존에 설치된 블록은 빼고 새로운 블록을 집어넣습니다.

블록은 1이 적힌 블록부터 숫자를 1씩 증가시키며 순서대로 설치합니다. 예를 들어 1이 적힌 블록은 2, 3, 4, 5, ... 인 위치에 우선 설치합니다. 그 다음 2가 적힌 블록은 4, 6, 8, 10, ... 인 위치에 설치하고, 3이 적힌 블록은 6, 9, 12... 인 위치에 설치합니다.

이렇게 3이 적힌 블록까지 설치하고 나면 첫 10개의 블록에 적힌 번호는 [0, 1, 1, 2, 1, 3, 1, 2, 3, 2]가 됩니다.

그렙시는 길이가 1,000,000,000인 도로에 1부터 10,000,000까지의 숫자가 적힌 블록들을 이용해 위의 규칙대로 모두 설치 했습니다.

그렙시의 시장님은 특정 구간에 어떤 블록이 깔려 있는지 알고 싶습니다.

구간을 나타내는 두 정수 begin, end 가 매개변수로 주어 질 때, 그 구간에 깔려 있는 블록의 숫자 배열을 return하는 solution 함수를 완성해 주세요.

---

제한 사항

• 1 ≤ begin ≤ end ≤ 1,000,000,000
• end - begin ≤ 5,000

---

입출력 예

beginendresult

• begin : 1
• end : 10
• result : [ 0, 1, 1, 2, 1, 3, 1, 4, 3, 5]

---

입출력 예 설명

---

[접근 방법]

문제만 잘 이해한다면, 구현은 전혀 어렵지 않은 문제다.

문제에서 주의할 사항에 대해 정리해보자면,

• 블록에 적힌 번호가 n 일 때, 가장 첫 블록은 n * 2번째 위치에 설치합니다. 그 다음은 n * 3, 그 다음은 n * 4, ...위치에 설치합니다. 기존에 설치된 블록은 빼고 새로운 블록을 집어넣습니다.
• 블록은 1이 적힌 블록부터 숫자를 1씩 증가시키며 순서대로 설치합니다.
• 그렙시는 길이가 1,000,000,000인 도로에 1부터 10,000,000까지의 숫자가 적힌 블록들을 이용해 위의 규칙대로 모두 설치 했습니다.
  => 길이가 10억이지만, 사용된 숫자의 최대값은 1천만 이다.

여기서 한 가지 잘 생각해야되는 부분은, 마지막 문구이다.
(길이가 10억이지만, 사용된 숫자의 최대값은 1천만 이다.)
입출력 예로 제공된 표를 참고해, 20까지만 더 진행해보도록 하자.

 

최상단 노란색 행은 도로를 의미한다.
좌측 하늘색 열은, 설치하는 블록을 의미한다.

 

위 표를 참고하면, 다음과 같은 규칙을 찾을 수 있다.

• 길이 소수 (Prime Number) 인 경우, 1
• 소수가 아닌 경우, 1보다 큰 최소 제수 (나눌 수 있는 수)
• begin 과 end 값이 결과에 영향을 주지는 않는다. (해당 범위만 가지고 찾아내면 됨)

이 규칙만 발견한다면, 구현은 매우 간단하다.

 

---

[풀이 소스]

    import java.util.*;
    class Solution {
        public int[] solution(long begin, long end) {

            int size = (int) (end - begin + 1);
            int[] answer = new int[size];

            int idx = size - 1;
            for(long i = end; i >= begin; i--) {
                answer[idx] = getMinimumDvidable(i);
                idx--;
            }

            return answer;
        }
        public int getMinimumDvidable(long number) {
            if(number == 1) return 0;

            List<Integer> temp = new ArrayList<Integer>();
            for(int i = 2; i <= Math.sqrt(number); i++) {
                if(number % i == 0 ) {
                    //!주의! 길의 범위는 10억이나, 블록의 최대값은 1천만
                    if(number / i <= 10000000) {
                        return (int)number / i;
                    } else {
                        temp.add(i);
                    }
                }
            }

            if(temp.size() > 0) {
                temp.sort((o1, o2) -> o2 - o1);
                return temp.get(0);
            }

            //소수
            return 1;
        }
    }