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

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

코딩테스트 연습 - n^2 배열 자르기

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {
        int cnt=0;
        int[] answer=new int[(int)(right-left+1)];
        for (long i=left; i<=right; i++){
            int r=(int)(i/n);
            int c=(int)(i%n);
            if (r+1>=c+1){
                answer[cnt++]=r+1;
            }
            else{
                answer[cnt++]=c+1;
            }
        }
        return answer;
    }
}

그대로 구현한다면 시간초과가 뜰 것이다. n^2가 10^14 라서 그렇다.

이 문제의 포인트는 배열의 n번째 수가 2차원 배열의 몇번째에 해당하고, 그 법칙을 찾아내는 것이다.

 

i번째 수를 구한다고 하면, i/n하면 행 번호, i%n하면 열 번호가 나오는데 이 문제의 규칙은

행 번호>=열 번호일 경우 행 번호를 따라가고, 행 번호<열 번호일 경우 열 번호를 따라간다는 점이다. 

이를 이용해서 answer에 넣어준다.