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

문제

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

첫 접근

• n행 n열의 크기를 가진 배열에 값을 채워넣을 방법을 고민했다.
  • n의 범위가 최대 10^7이었기에 o(n^2)의 경우 시간 초과가 발생할 거라 생각했다.

배운 점

	0	1	2
0	1	2	3
1	2	2	3
2	3	3	3

• 위의 표를 보면, 배열값은 (행의 인덱스와 열의 인덱스) 중 더 큰 값 + 1 로 표현됨을 알 수 있다.
• 행의 경우는 (현재 위치 / 전체 배열의 크기), 열 = (현재 위치 % 전체 배열의 크기)로 표현된다.
• 위의 규칙대로 값이 채워지는 배열을 left ~ right 만큼 나타내야 하므로 위의 규칙대로 값을 구해주며 left ~ right 만큼 출력한다.

코드

import java.util.*;

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