[프로그래머스 코딩테스트] n^ 2 배열 자르기(Java)

  문제 설명

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

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i = 1, 2, 3, …, n에 대해서, 다음 과정을 반복합니다.
   1. 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]

class Solution {
    public int[] solution(int n, long left, long right) {
        int[] answer = new int[(int)(right - left + 1)];
        for (int i = 0; i < answer.length; i++) {
            int n1 = (int)(left % n + 1);
            int n2 = (int)(left / n + 1);
            left++;
            answer[i] = Math.max(n1, n2);
        }
        return answer;
    }
}​

  배열 answer를 생성합니다. 크기는 rigth - left + 1로 지정합니다. left와 right는 long이므로 int로 형변환을 해줍니다.

  for문이 answer의 길이만큼 순회합니다.

  변수 n1과 n2를 생성합니다. 각각 left를 n으로 나눈 나머지에 1을 더한 값과 left를 n으로 나눈 값에 1을 더한 값을 할당합니다.

  left가 증가합니다.

  answer의 i 번째 원소에 Math 클래스의 max 메소드를 이용하여 n1과 n2 중 큰 값을 할당합니다.

 

  신재권님의 코드를 참고했습니다.

  https://school.programmers.co.kr/questions/42681

 

  메모리 초과로 실패한 코드

import java.util.Arrays;
class Solution {
    public int[] solution(int n, long left, long right) {
        int[][] arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = Math.max(i + 1, j + 1);
            }
        }
        int index = 0;
        int[] answer = new int[(int)(right - left + 1)];
        for (long i = left; i <= right; i++) {
            int row = (int)(i / n);
            int col = (int)(i % n);
            answer[index++] = arr[row][col];
        }
        return answer;
    }
}