[programmers] n^2 배열 자르기 - Java

n^2 배열 자르기

문제 설명

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.

2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
• 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.

3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.

4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.

제한사항

• 1 ≤ n ≤ 10
7

• 0 ≤ left ≤ right < n
2

• right - left < 10
5

입출력 예

입출력 예 설명

• 다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

• 다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

처음 시도한 코드

import java.util.*;
class Solution {
    public int[] solution(int n, long left, long right) {
        int[][] arr = new int[n][n];
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i==0){
                    arr[i][j] = j+1;
                    list.add(j+1);
                }
                else{
                    if(j<i){
                        arr[i][j] = arr[i-1][j] + 1;
                        list.add(arr[i-1][j] + 1);
                    }else{
                        arr[i][j] = arr[i-1][j];
                        list.add(arr[i-1][j]);
                    }
                }
            }
        }
        int[] ans = new int[(int)(right-left)+1];
        int index = 0;
        for (int i = (int)left ; i <= (int)right ; i++) {
            ans[index] = list.get(i);
            index++;
        }
        return ans;
    }
}

개선한 코드

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {
        List<Integer> result = new ArrayList<>();
        for (long i = left; i <= right; i++) {
            long row = i / n;
            long col = i % n;
            int value = Math.max((int) row, (int) col) + 1;
            result.add(value);
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

핵심 키워드

• 처음 작성한 코드는 이중 반복문으로 인한 메모리 초과로 테스트 통과에 실패했다.

• 해당 문제를 해결하기 위해 n행이 있는 가상 배열에서 해당 행과 열 인덱스를 계산한 후, 행과 열 인덱스를 이용해 현재 인덱스의 값을 계산하는 방식으로 문제를 해결할 수 있었다.

결론!