정수n,left,right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.
n행n열 크기의 비어있는 2차원 배열을 만듭니다.
i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
1행 1열부터i행i열까지의 영역 내의 모든 빈 칸을 숫자i로 채웁니다.
1행, 2행, ...,n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 1차원 배열을arr이라 할 때,arr[left],arr[left+1], ...,arr[right]만 남기고 나머지는 지웁니다.
정수n,left,right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.
제한사항
1 ≤n≤ 107
0 ≤left≤right< n2
right-left< 105
입출력 예
n left right result
3
2
5
[3,2,2,3]
4
7
14
[4,3,3,3,4,4,4,4]
입출력 예 설명
입출력 예 #1
다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.
입출력 예 #2
다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.
import java.util.*;
class Solution {
public int[] solution(int n, long left, long right) {
int diff = (int)(right-left);
int[] answer = new int[diff+1];
int idx = 0;
long num = left;
for(long i=num; i<=right; i++){
int l = (int)(num/n);
int r = (int)(num%n);
answer[idx++] = Math.max(l+1,r+1);
num++;
}
return answer;
}
}
배열의 index는 int값으로 이루어져 있으므로 주어진 조건에 따라 2차원 배열을 선언하면 배열의 크기가 int 범위의 최댓값보다 커지게 되어 메모리 초과가 발생한다. 따라서 right - left 값의 크기는 int 범위 내에 있으므로 해당 값에 대해서 배열을 생성해야한다.
