[Java/자바] 프로그래머스 Lv2 - n^2배열 자르기

문제 설명

정수 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]

 

입출력 예 설명 : solution(3, 2, 5) 일 때

---

Solution.java

이 문제는 위 애니메이션 처럼 2차원 배열을 직접 만들어 실행시키게 되면 n이 10^7까지 이므로 메모리가 부족하거나 시간 초과가 발생할 것입니다.

그래서 아래처럼 규칙을 이용하여 간단하게 답을 찾는 방법이 있습니다.

 

1	2	3
2	2	3
3	3	3

(행, 열)의 값을 보면

(1, 1)는 1

(2, 2)는 2

(3, 2)는 3

(1, 2)는 2

으로 (행, 열)중 가장 큰 값 Math.max(행, 열)이 그 행열의 값이 된다는 것을 알 수 있습니다. 

 

위 2차원 배열을 1차원 배열로 나열하면 다음과 같습니다.

인덱스	0	1	2	3	4	5	6	7	8
행열의 값	1	2	3	2	2	3	3	3	3

여기서 left(2)부터 rigth(5)까지만 남기고 나머지는 지운다면 값은 [3, 2, 2, 3]이 되는데

우리는 해당 행열의 값만 알면 됩니다.

2번째 인덱스의 값 3은 (1, 3)으로 해당 값의 행 열을 구하는 식을 구하면 다음과 같습니다.

행 : 해당 인덱스 / n + 1 
열 : 해당 인덱스 % n + 1

 

이 식을 이용하여 원하는 행열의 값을 구하면

1차원 배열의 3번째 값을 구한다 가정했을 시, Mah.max(3 / 3 + 1, 3 % 3 + 1) => 2가 됩니다.

 

import java.util.Arrays;

public class n2배열자르기 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(solution(3, 2, 5)));
        System.out.println(Arrays.toString(solution(4, 7, 14)));
    }

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

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

        return answer;
    }
}