Skip to main content

[Java] 87390 n^2 배열 자르기

📝 n^2 배열 자르기

1. 문제 요약

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

  1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
  2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
  3. 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
  4. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
  5. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.
  6. 정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

image.png

image.png

image.png

image.png

2. 접근 방법

어렵다. 직접 n * n 배열을 다 만들면 메모리 초과가 날 수 있으니까, 수학적인 규칙을 찾아야 한다.

문제에서 말한 규칙은

i행 i열까지 숫자 i로 채운다

이걸 실제로 채워보면 n = 3일 때

1. i = 1 → (0, 0) 채움

1 0 0
0 0 0
0 0 0

2. i = 2 → (0, 1), (1, 0), (1, 1) 채움

1 2 0
2 2 0
0 0 0

3. i = 3 → (0, 2), (1, 2), (2, 0), (2, 1), (2, 2) 채움

1 2 3
2 2 3
3 3 3
  • (0,0) → max(0,0)+1 = 1
  • (0,1) → max(0,1)+1 = 2
  • (2,0) → max(2,0)+1 = 3
  • (2,2) → max(2,2)+1 = 3

행과 열 중 더 큰 값을 넣는 방식이다.
즉, "행과 열 중 더 큰 값을 넣는다"는 말은 좌표 (i, j)에 들어갈 값 = max(i, j) + 1 이라는 뜻이다.

1 2 3
2 2 3
3 3 3


그리고 우리는 left ~ right구간만 뽑아야 하니까 전체 배열을 만들 필요가 없이 인덱스를 좌표로 변환하면 된다.

이 때 필요한 변수가 idx, left, right 이다.

2차원배열이랑 1차원 인덱스 매핑하는 법

  • 문제에서 만드는 1차원 배열은 n×n 2차원 배열을 일렬로 펼친 것이다.
  • n=4라면 2차원 배열은 이렇게 생겼다. 
행\열 | 0  1  2  3
-------------------
0     | 1  2  3  4
1     | 2  2  3  4
2     | 3  3  3  4
3     | 4  4  4  4

그리고 1차원 배열은 이렇게 펼쳐진다

0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15
1  2  3  4  2  2  3  4  3  3  3  4  4  4  4  4

여기서 우리가 필요한 것은 1차원 배열에서의 위치이다. 이걸 idx라고 해보자.

1차원 배열에서의 인덱스 idx = 2차원 배열에서 값의 “몇 번째 위치인지”를 나타내는 숫자이다.
예를 들면 idx = 6은 1차원 배열의 6번째 위치라는 뜻이다. 0부터 세니까 7번째 값이다.

위의 2차원 배열에서 idx 6에 담긴 value값은 3이다.
1차원배열의 idx = 6에 대응하는 2차원 배열 인덱스는 (1,2) 이다.

이걸 점화식으로 구할 수 있다.

  • 행(row) = idx를 n으로 나눈 몫 → idx / n
  • 열(col) = idx를 n으로 나눈 나머지 → idx % n
  • idx = 6 을 구하면 max(row, col) + 1 = max(1,2) + 1 → 값 = 3
row = idx / n = 6 / 4 = 1
col = idx % n = 6 % 4 = 2

3. 정답코드

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

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

        return answer;
    }
}

4. 오답 / 어려웠던 점

class Solution {
    public int[] solution(int n, long left, long right) {
        long size = (right - left + 1);
        int[] answer = new int[size];
        
        for (int i = 0; i < size; i++) {
            long idx = left + i; // 전체 배열에서 인덱스
            long row = (idx / n); // 행
            long col = (idx % n); // 열
            answer[i] = Math.max(row, col) + 1;
        }
        
        return answer;
    }
}

image.png

자바에서 배열 길이와 배열 값 타입 모두 int여야 한다.

  • long 타입으로 설정하면 컴파일 오류가 난다.
  • 제한사항으로 n이 10의 7제곱까지라서 숫자가 커지기 때문에 long타입으로 풀었는데, (int)로 형변환 해야 한다.
int size = (int)(right - left + 1);
  • Math.max(row, col) + 1부분도 row와 col이 long이기 때문에, Math.max(long, long)은 long을 반환한다.
  • 배열에 넣으려면 이 부분도 int 타입으로 변경해야 한다.
answer[i] = (int)(Math.max(row, col) + 1);



Back to top