n^2 배열 자르기

🕵️문제설명

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

n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 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

🔎로직설명

fun solution(n: Int, left: Long, right: Long): MutableList<Int> {
        var result = ArrayList<Int>()
        (1..n).forEach {
            val row = IntArray(n){0}
            for (i in row.indices){
                if (i+1 <= it){
                    row[i] = it
                }else row[i] = i+1
            }
            result.addAll(row.toList())
            println("${result.joinToString("")}")
        }
        return result.subList(left.toInt(),right.toInt()+1)
    }

기본적인 구성에 따라 일단 만들어 봤다

1234
2234
3334
4444

이런 식으로 행렬을 만든 후 left번째에서 right번째까지 배열을 나타낸다

4 7 14면 43334444 가 남는데 1234223 처럼 쓰지도 않는 부분이 메모리를 너무 차지한다

행렬을 만들지 않고 원하는 부분만 딱 때오는 방법이 뭐가 있을까?

보면 1번째 행을 숫자가 오름차순으로 제대로 나왔있다

그런데 2번째 부터 2234 이런식으로 나온다

3번째 행은 3334 이걸보면 행의 숫자들은 행의 순서보다 클 수가 없다는걸 알수 있다

우리는 left에서 right까지의 숫자들을 원한다 그럼 left는 몇행 몇열일까?

left를 n만큼 나눠주고 거기에 1을 더하면 행을 구할수 있고 열은 나머지를 구해주면 구할수 있다

fun solution(n: Int, left: Long, right: Long): MutableList<Int> {
        var result = ArrayList<Int>()
    (left..right).forEach {
        val row = it / n
        val col = it % n
        result.add(maxOf(row,col).toInt() + 1)
    }
    return result
    }

열을 구했는데 그 수가 행보다 작으면 안되니까 maxOf로 구분해주고 리스트에 추가했다

응용하면 더 줄일 수 있다

fun solution(n: Int, left: Long, right: Long): IntArray {
    return (left..right).map { 
        (maxOf(it/n , it % n)+1).toInt()}.toIntArray()
    }

result를 없에고 map을 써서 바로 컬렉션을 만든다

row와 col을 따로 만들지 않고 maxOf에 수식을 바로 넣어주면 좀 더 간략하게 작성이 가능하다