문제
그렙시에는 숫자 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
class Solution {
public int[] solution(long begin, long end) {
int[] answer = new int[(int)(end-begin+1)];
int idx = 0;
for(int i = (int)begin; i <= end; i++) {
int max = 0;
for(int j = 1; j <= Math.sqrt(i); j++) {
if(i == 1) { break; }
if(i % j == 0) {
max = Math.max(max, j);
if(i / j != i && i / j <= 10000000) {
max = Math.max(max, i/j);
}
}
}
answer[idx++] = max;
}
return answer;
}
}생각보다 굉장히 애먹은 문제였다.
생각보다 쉬워보였는데, 중간에 있는 블럭이 어떤 상태인지 알아야 한다는 점을 계속 생각하다보니 꽤나 어려웠다.
처음 생각한 방법은,
block은 1부터 시작하니 1로 초기화 하고, setBlock이란 변수에 end/block이 2 이상이면 end/block 값을, 아니라면 block 값을 저장했다.
이유는 end의 절반까지만 확인해도 되기 때문이였다. 그 이후는 *2를 하면 end 이상의 값이 되어버린다.
그리고 setBlock을 block 값만큼 빼가면서 begin~end 길이만큼의 배열에 저장을 했다.
예를들어 10~21 이라고 한다면 21/1 = 21 이므로 setBlock 변수에 21을 저장 후 1씩 빼나갔다. 배열은 0~11 이므로 setBlock-begin (21-10) 으로 배열의 맨 뒷부분부터 저장하며 진행한다.
그리고 setBlock이 begin 이하가 되면 block을 1 증가시키고 해당 과정을 다시 반복한다.
최종적인 종료 조건과 제대로된 로직은 사실 기억이 안난다. 오늘 아침에 생각해냈던 방법이지만 비효율적이라면서 퇴짜맞은 코드라 이 설명도 사실 부질없는 짓이다.
그래서 어찌할까 하면서 디버깅하다보니 뭔가 눈에 많이 익은 모습이 보였다.
그 모습은 마치 n의 약수와 비슷해보였다.
그래서 begin~end의 약수를 뽑아 관찰해보니
각 수의 약수 중, 자기 자신을 제외한 값 중 최대값을 배열에 저장하면 되는 것이였다.
그리고 소인수는 그냥 1을 저장하면 되는 것이였다.
예를 들어 6의 약수는 1, 2, 3, 6 이고, 자기 자신 6을 제외한 값 중 최대값은 3이므로 배열에 3을 저장하면 된다.
1번부터 진행하니 1은 무조건 0번 인덱스에 0, 즉, 저장하지 않고,
2는 약수가 1, 2 소인수이므로 1번 인덱스에 1,
3은 약수가 1, 3 소인수 -> 2번 인덱스 1,
4는 1, 2, 4 이므로 3번 인덱스에 2,
5는 4번 인덱스에 1,
6은 5번 인덱스에 3
이런식이다.
그런데 13번 문제가 해결되지 않아서 결국 이건 힌트의 힘을 빌렸다....
이유는 블록이 최대 10,000,000까지의 숫자만 사용했다라는 점인데, 이에 대한 자세한 설명은 https://school.programmers.co.kr/questions/43745여기서 누군가 자세하게 설명해주셨다.
여담으로, 프로그래머스 문제를 풀며 처음으로 최대 점수를 얻었다. 무려 8점;;
출처
https://school.programmers.co.kr/learn/courses/30/lessons/12923