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

코딩테스트 연습 - n^2 배열 자르기

문제 설명

정수 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 ≤ 10⁷
• 0 ≤ left ≤ right < n²
• right - left < 10⁵

풀이

To-Do 리스트

결과

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {
        int[] answer = {};
        int[][] nnrr = new int[n][n];
        int[] res = new int[n*n];
           
        for(int i = 0; i< nnrr.length; i++){
            for(int j = 0; j < nnrr[i].length; j++){
                nnrr[j][i] = j+1;
                if(nnrr[i][j] == 0){
                    nnrr[i][j] = j+1;
                }
            }
            System.arraycopy(nnrr[i], 0, res, n*i, n);
        }
        
        int a = 0;
        int ir = Long.valueOf(right).intValue();
        int il = Long.valueOf(left).intValue();
        int len = ir-il+1;
        answer = new int[len];
        
        for(int k = il; k <= ir; k++){
            answer[a++] = res[k];
        }
        return answer;
    }
}

알게 된 점

메모리초과. 그럴거같긴했는데..
이중 배열을 만듬으로써 메모리부족해짐.

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {
        int ir = Long.valueOf(right).intValue();
        int il = Long.valueOf(left).intValue();
        int len = ir-il+1;
        
        int[] answer = new int[len];

        for(int k = 0; k < answer.length; k++){
            int x = (int)(left/n) + 1;
            int y = (int)(left%n) + 1;
            left++;
            answer[k] = Math.max(x,y);
        }
        return answer;
    }
}