2023.12.01(금) TIL

오늘은 programmers 에서 n^2배열 자르기 문제를 풀었다.
n=3, left=2, right=5라고 주어졌을때 nXn 행렬을 만드는데,

인덱스가 left=2부터 right=5까지인 3,2,2,3을 출력시켜주면 되는 문제다.

3단계레벨 문제치고 어렵지 않다 생각했고, 2차원 배열을 만들어서 각각의 숫자를 집어넣고, 해당값들을 리스트에 다 넣어서 일렬로 펼쳐준후에, 원하는 인덱스 값을 추출하는 방식으로 풀어야 겠다 생각했고, 성공적이였다.

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

        val array = Array(n){ IntArray(n) }
        val myList = mutableListOf<Int>()
        for(i in 0 until n){
            for(j in 0 until n){
                var maxValue = maxOf(i,j) + 1
                array[i][j] = maxValue
                myList.add(maxValue)
            }
        }
        val finalList = mutableListOf<Int>()
        for(k in left..right){
            var wantValue = myList.get(k.toInt())
            finalList.add(wantValue)
        }
        return finalList.toIntArray()
    }
}

2중 for문을 사용해서 배열에 값을 넣어주고, 원하는 값을 성공적으로 추출할수 있었다. 하지만 이 문제에는 제한사항이 있었다..

n의 범위가 너무 크다.. 최대
10000000X10000000크기의 행렬이 만들어진다.. 위 방법으로 진행하면 2중 for문을 돌려 너무 느리고, 메모리 초과가 나오게 된다..

해결하기 위해서는 내가 추출하려는 부분만! 값을 넣어 가져와야한다. 그래서 다시 작성한 코드는

class Solution {
    fun solution(n: Int, left: Long, right: Long): IntArray {
        val answer = IntArray((right - left + 1).toInt())
        for (i in left..right) {
            val row = (i / n).toInt()
            val col = (i % n).toInt()
            answer[(i - left).toInt()] = maxOf(row, col) + 1
        }
        return answer
    }
}

n=3이라고 했을때,
(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)
이런 행렬이 만들어 진다.각 값에는 i,j의 최대값에서 +1된 값이 들어갈거고, 해당부분은 (i / n),(i % n)를 이용해서 위치를 구할 수 있었다.

제한사항에 막혀 오랜시간 걸린 문제를 해결하니 뿌듯하며 힘들었다.... 그후 다른 사람들이 문제를 푼걸 보다가 깜짝 놀란 코드가 하나 있다..

import kotlin.math.max
class Solution {
    fun solution(n: Int, left: Long, right: Long): IntArray {
        return (left..right).map { (max(it / n, it % n) + 1).toInt() }.toIntArray()
    }
}

코드를 읽으니 그대로 쭉 이해가 가고.. 아 짱이다 라는 소리가 나오는 코드였다.. 나도 이렇게 쉽게 풀고 넘어가보고싶다..