# \[99클럽 코테 스터디 1일차 TIL] 프로그래머스 - n^2 배열 자르기

### \[level 2] n^2 배열 자르기 - 87390

[문제 링크](https://school.programmers.co.kr/learn/courses/30/lessons/87390?language=java)

#### 성능 요약

메모리: 85.9 MB, 시간: 7.41 ms

#### 문제 설명

정수 `n`, `left`, `right`가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

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]`만 남기고 나머지는 지웁니다.

정수 `n`, `left`, `right`가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

***

#### 제한사항

* 1 ≤ `n` ≤ 10^7
* 0 ≤ `left` ≤ `right` < n^2
* `right` - `left` < 10^5

***

#### 입출력 예

| n | left | right | result              |
| - | ---- | ----- | ------------------- |
| 3 | 2    | 5     | `[3,2,2,3]`         |
| 4 | 7    | 14    | `[4,3,3,3,4,4,4,4]` |

***

**입출력 예 설명**

**입출력 예 #1**

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

![ex1](https://grepp-programmers.s3.amazonaws.com/production/file_resource/103/FlattenedFills_ex1.gif)

***

### 의식의 흐름

처음엔 어떻게든 2차원 배열을 만들려고 했는데 예제의 그림처럼 만들기가 어려웠다.

그러고보니 반환 값은 1차원 배열이니까 굳이 2차원 배열을 만들 필요가 있을까? 란 생각이 들어서 한번에 1차원 배열을 만들기로 결정했다.

만들려고 보니 어차피 2차원 배열을 만들 줄 알아야 했다. 노트에 적어놓고 뚫어지게 쳐다보니 규칙이 보였다.

* 1행 1열 - 1
* 1행 2열 - 2
* 2행 2열 - 2
* 2행 3열 - 3
* 3행 1열 - 3

행과 열 중 큰 값이 해당 위치의 값이 된다. `Math.max()` 함수를 이용하면 되겠다. 이제 한번에 1차원 배열만 만들면 된다.

일단 반환해야할 배열 크기는 `right - left + 1` 이란걸 알 수 있다. 문제 제한 사항에서도 친절하게 `right - left` 는 10^5 미만 즉, 정수형 범위 안에 있다고 알려준다. 괜히 알려주는게 아니라고 생각했다.

그리고 예제 애니메이션에서 보여주는 것처럼 1차원 배열에서 `left` 인덱스 위치부터 `right` 인덱스 위치까지 값만 구해서 반환하면 끝이다.

`left` 인덱스 위치의 행과 열 값만 알면 값은 바로 알 수 있다. 여기서 막혀서 다른 분들의 문제 풀이를 참고하여 문제를 해결했다. 아래는 풀이 코드이다.

```java
class Solution {
    public int[] solution(int n, long left, long right) {
        int len = (int) (right - left);
        int[] answer = new int[len + 1];

        int idx = 0;
        for (long i = left; i <= right; i++) {
            answer[idx++] = (int) Math.max(i/n, i%n) + 1;
        }
        
        return answer;
    }
}
```

코드를 보면 행 값은 `i/n` 이고 열 값은 `i%n` 인걸 알 수 있다.

### 돌아보기

위의 행 값과 열 값의 규칙을 찾게 되는 과정이 이해되지 않아 ChatGPT 에게 물어봤다.\
답변을 통해 알게된 건 1차원 배열의 인덱스 위치와 2차원 배열 좌표 사이의 관계성을 생각해야 했다는 것이다.

예를 들어 3-3 크기의 2차원 배열을 만든다면 1차원 배열의 인덱스 값과 2차원 배열의 좌표 값은 아래와 같을 것이다.

| 1차원 배열의 인덱스 값 | 2차원 배열의 좌표 값 |
| :-----------: | :----------: |
|       0       |    (0, 0)    |
|       1       |    (0, 1)    |
|       2       |    (0, 2)    |
|       3       |    (1, 0)    |
|       4       |    (1, 1)    |
|       5       |    (1, 2)    |
|       6       |    (2, 0)    |
|       7       |    (2, 1)    |
|       8       |    (2, 2)    |

좌표 값이 특정 규칙에 따라서 2차원 배열의 크기만큼 반복되는걸 볼 수 있다. 0번째와 3번째, 6번째 인덱스 값과 관계되는 2차원 배열의 행 값을 보면 2차원 배열의 크기로 나누면 그 몫으로 맞아떨어지는 것으로 보인다.

위와 같이 유추를 통해 규칙성을 찾으면 될 것 같다.

#### 다음에는

1. 머리로 풀려고 하지 말기
2. 노트에 적는걸 귀찮아 하지 말기
3. 시간에 쫓겨 조급해 하지 말기

***

\#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL