[프로그래머스] n^2배열 자르기

       문제 요약      

- 문제

https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

 

 

- 제한 사항

1 <= n <= 10^7

0 <= left <= right < n^2

right - left < 10^5

 

         아이디어        

 

arr[left], arr[left + 1] , ... , arr[right] 

 

         소스코드        

 

[메모리초과] 처음 풀이 >> 문제에서 나온 그대로 구현  

제한 사항에서 n이 크기 때문에 배열을 생성해서 구하면 메모리 초과가 난다

import java.util.*;
class Solution {
    static int[][] box;
    public int[] solution(int n, long left, long right) {
        box = new int[n][n];
        for(int value = 1; value <= n; value++) {
            for(int i = 0; i < value; i++) { 
                for(int j = 0; j < value; j++) {
                    if(box[i][j] == 0) {
                        box[i][j] = value;                    
                    }
                }
            }
        }
        int[] answer = new int[(int)(right-left+1)];
        for(long x = left; x <= right; x++) {
            answer[(int)(x - left)] = box[(int)(x / n)][(int)(x % n)];
        }
        
        return answer;
    }
    
    static int[] copy(int[] arr, long left, long right) {
        int[] copyed = new int[(int)(right - left + 1)];
        for(int i = (int)left; i <= (int)right; i++) {
            copyed[i-(int)left] = arr[i];
        }
        return copyed;
    }
}

 

박스에 값이 채워지는 규칙을 찾아봤다

 

행과 열 중 큰 값 + 1이 그 칸에 들어가는 숫자가 된다 

import java.util.*;
class Solution {
    public int[] solution(int n, long left, long right) {
     
        int[] answer = new int[(int)(right-left+1)];
        for(long x = left; x <= right; x++) {
            answer[(int)(x - left)] = (int) Math.max(x / n , x % n) + 1;
        }
        
        return answer;
    }
    
    static int[] copy(int[] arr, long left, long right) {
        int[] copyed = new int[(int)(right - left + 1)];
        for(int i = (int)left; i <= (int)right; i++) {
            copyed[i-(int)left] = arr[i];
        }
        return copyed;
    }
}