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

문제와 영상처럼 이차원 배열을 구현하여 직접 대입 후 문제를 해결하려고 시도한다면 시간초과가 발생 할 것 이다. 

제한사항 중 1 <= n <= 10^7 의 범위 -> 배열에 삽입하는데 O(n^2) 시간 발생  

 

따라서 2차원 배열을 직접 구현하지 않고 1차원 배열을 이용해 문제를 풀어야 한다. 

규칙을 찾았다 ! !

n이 4일 때의 2차원 배열

첫 번째 규칙, 여기서 n x n 배열일 때, (i / n) 은 행의 값이 되고, (i % n)은 열의 값이 된다.

                     위의 사진으로 예시를 들면, 7/4 = 1  행의 값은 1   //////   7%4 = 3 열의 값은 3 

두 번째 규칙, 배열의 자리의 값은 배열 인덱스의 (MAX(행,렬)+1)의 값이다! 

                    예를 들자면,   (1,3)의 값은 4 !  (0,3)의 값은 4 ! , (1,2)값은 3 ! , (2,3)의 값은 4 이다 ! 

 

위와 같은 두가지 규칙으로 문제를 해결했다. 

전체 코드

fun solution(n: Int, left: Long, right: Long): IntArray {

    var list= arrayListOf<Int>()

    for(i in left.. right){
        val row=i/n
        val column=i%n

        list.add(maxOf(row,column).toInt()+1)
    }

    return list.toIntArray()
}