n^2 배열 자르기

문제

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

---

풀이

우선 메모리 효율 문제이기 때문에
문제에서 알려준 방식으로 2차원 배열에서 1차원 배열로 변경하면 안된다!

따라서 마지막에 반환되는 left ~ right 크기의 배열만 놓고 계산을 진행해야한다.

그러면 어떻게 계산해야 할까? 🤔

2차원 배열에 들어가는 규칙을 보면 된다.

	1열	2열	3열
1행	1	2	3
2행	2	2	3
3행	3	3	3

(1,1) -> 1
(1,2) (2,1) (2,2) -> 2
(1,3) (2,3) (3,1), (3,2) (3,3) -> 3

1. n번째 행에서 n열보다 같거나 작은 곳만 n으로 채워진다
2. n열보다 큰 곳은 열의 위치에 맞춰서 채워진다.

즉, 2번째 행에서 2열보다 같거나 작은 곳은 2로 채워진다.
2열보다 큰 곳은 열의 위치에 맞춰서 채워진다. (3열 -> 3)

1차원 배열에 대입 📝

2차원에서 구한 규칙을 1차원 배열에 대입하려면
1차원 인덱스를 사용하여 몇번째 행,열 인지를 구해야 한다.

#인덱스	0	1	2	3	4	5	6	7	8
값	1	2	3	2	2	3	3	3	3

인덱스를 통해 몇번째 행인지를 구하는 법은
= ((인덱스) / (2차원 배열의 크기)) + 1

즉, 0,1,2인 경우 3으로 나누면 몫이 0이라서 +1을 하면 1번째 행이 된다.
3,4,5 -> 몫 = 1 + 1 = 2번째 행
6,7,8 -> 몫 = 2 + 1 = 3번째 행

몇번째 열인지 구하는 법
= (인덱스) % (2차원 배열의 크기)

즉, 0,3,6 인 경우 3으로 나눈 값의 나머지는 0(1열)이 된다.
1,4,7 -> 나머지 = 1 (2열)
2,5,8 -> 나머지 = 2 (3열)
(인덱스이기 때문에 원래의 열의 값보다 -1 처리)

따라서 만약 인덱스의 열이 행보다 작을 경우, 행의 값을 넣고
만약 크거나 같은 경우, 열의 값을 넣으면 된다.

3,4,5 로 보면
3 = 2행, 0(1열) 이므로, 열이 행보다 작기 때문에 행의 값(2)를 넣는다.
4 = 2행, 1(2열) 이므로, 똑같이 행의 값(2) 를 넣는다.
5 = 2행, 2(3열) 이므로, 열과 행이 같이 때문에 열의 값(3)을 넣는다.

#인덱스	3	4	5
값	2	2	3

left ~ right의 배열에 공식을 대입 🌈

마지막으로 메모리를 최소화 하기 위해 left ~ right 크기의 배열을 만들고
인덱스도 left부터 right까지로 놓아서 위에서 구한 공식으로 대입한다.

int [] array = new int[(int) (right-left+1)]; 

---

코드

public class N_2Array {
    public int[] solution(int n, long left, long right) {
        int [] array = new int[(int) (right-left+1)]; 
        //메모리를 최소화 하기 위해 필요한 만큼의 배열만 제작

        //위치한 인덱스마다 어떤 값이 들어오는지에 대한 연관성을 계산
        int index = 0;
        for (long i = left; i<=right; i++){
            int row = (int) ((i / n) + 1); //현재 위치 인덱스가 2차원 배열에서 몇번째 행인지를 계산
            if (i % n < row){ //i % n은 열의 위치 - 1
                //열의 위치가 행보다 작으면 행의 위치값을 넣는다.
                //만약 1번째 열, 2번째 행에 위치해 있다면 2를 넣는다는 것
                array[index] = row;
            } else {
                //열의 위치가 행보다 같거나 크면 그때부터는 열의 값을 넣는다.
                //만약 3번째 열, 2번째 행에 위치해 있다면 3을 넣는다.
                array[index] = (int) (i % n) + 1;
                //i%n이 0부터 시작했기 때문에 + 1
            }
            index ++;
        }
        return array;
    }
}