🎯문제
그렙시에는 숫자 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
입출력 예
| begin | end | result |
|---|---|---|
| 1 | 10 | [0, 1, 1, 2, 1, 3, 1, 4, 3, 5] |
입출력 예 설명
입출력 예 #1
다음과 같이 블럭이 깔리게 됩니다.
※ 공지 - 2019년 4월 07일 테스트케이스가 변경되었습니다.
※ 공지 - 2023년 2월 09일 지문과 테스트 케이스가 수정되었습니다. 기존에 통과되었던 코드가 통과되지 않을 수 있습니다.
✏️풀이
코드
import java.util.*;
class Solution {
public int[] solution(long begin, long end) {
// 시작위치, 종료위치, 인덱스
int start = (int)begin, last = (int)end, index = 0;
int[] answer = new int[last - start + 1];
// 시작위치부터 종료위치까지 반복문 진행
for(int i = start; i <= last; i++) {
boolean flag = false;
// 쌓이는 값들을 저장할 배열
List<Integer> list = new ArrayList<>();
// 루트(i)까지 반복을 진행하여 약수를 찾음
for(int j = 2; j <= Math.sqrt(i); j++) {
// 나누어 떨어진다면
if(i % j == 0) {
// 배열에 값을 넣어줌
list.add(j);
// 10000000까지의 숫자만 사용
if(i / j <= 10000000) {
answer[index++] = i / j;
flag = true;
break;
}
}
}
// 이미 값이 들어갔다면 continue
if(flag) {
continue;
}
// 값이 들어가지 않고 list에 값이 존재한다면
if(!list.isEmpty()) {
// list의 마지막 값을 넣어줌
answer[index++] = list.get(list.size() - 1);
continue;
}
// 두 경우 모두 해당하지 않을 때 1을 넣어줌
// 단 i가 1인 경우에는 0을 넣어줌
answer[index++] = i == 1 ? 0 : 1;
}
return answer;
}
}설명
단순구현하여 진행하였다.
long형의 begin과 end를 int형으로 바꿔 start와 last에 각각 저장해주었고, index 변수를 생성하였다.
반복문은 시작위치부터 종료위치까지 반복문을 진행한다.
flag라는 변수를 사용하여 값을 넣어줬는지 여부를 판단한다.
값이 들어가는 조건은 약수일 경우이다. 즉 나눴을 때 나머지가 0은 경우이므로 해당 조건에 성립하게 된다면 list에 값을 저장한다. 또한 10,000,000까지의 숫자만 사용을 한다고 했으므로 나눴을 때 몫이 10,000,000보다 크면 바로 넣지 않고 반복문을 계속 진행한다. 몫이 10,000,000보다 작거나 같다면 해당 값을 넣어주고 flag를 true로 바꿔준다.
반복문을 빠져나와서 값이 들어갔다면 continue를 진행하여 다음 위치에서 탐색을 진행한다.
값이 들어가지 않았다면 list에 저장된 값이 있는지 확인하고, 해당 값중 가장 마지막에 있는 값을 넣어준다.
예를 들어, 현재 i가 10이고 j가 2일 때 i % j == 0이라는 조건에 성립한다. 그렇다면 2를 list에 저장해주고 i / j를 계산해서 값을 비교한다. i / j = 5이므로 10,000,000보다 작은 값이다. 또한 해당 몫은 10의 약수들 중 가장 큰 수이고, 가장 맨 위에 쌓이는 블록이 된다. 따라서 answer에 해당 값을 저장한다.
만약 현재 i가 30,000,000이고 j가 2일 때 i % j == 0이라는 조건에 성립한다. 그렇다면 마찬가지로 2를 list에 저장해주고 i / j를 계산한다. i / j = 15,000,000이다. 이는 10,000,000보다 큰 값으로 해당 블록은 존재하지 않기 때문에 넘어가게 된다. 이런 식으로 2, 3만 약수가 되고 다른 약수들은 값이 넘어가게 된다면 가장 맨 위에 쌓이는 블록은 list에 저장된 값 중 가장 큰 값이 되기 때문에 list의 가장 마지막 부분을 answer 배열에 저장한다.
위의 두 경우 모두 해당하지 않을 경우에는 1을 넣어주는데 이때 현재 위치, 즉 i가 1이라면 그때는 0을 넣어준다.
위의 모든 반복이 끝난 뒤 answer 배열을 반환해주면 문제를 해결할 수 있다!
💡느낀 점
잘 읽어보지 않고 풀다가 놓친 조건들이 많아서 시간을 썼던 문제였다. 또한 조건들을 추가할 때마다 코드들을 대폭 수정해야했기에 처음부터 문제를 잘 읽어보고 풀 걸.. 이라는 생각이 들게 한 문제였다. 우여곡절 끝에 해결은 했지만 최적화된 코드는 아닌 것 같아서 다른 블로그들을 보면서 조금 더 공부를 해봐야할 것 같다.
링크
