릿코드 1424. Diagonal Traverse II 코틀린

문제:

0,0
0,1 1,0
0,2 1,1 2,0
0,3 1,2 2,1 3,0
순서로 출력

 

리스트의 갯수+마지막 리스트의 갯수-1로 반복횟수잡으면?->중간에 가장 큰거있으면?

리스트의 갯수+가장 긴 리스트의 사이즈 -1로 반복횟수잡기

 

타임아웃

class Solution {
    fun findDiagonalOrder(nums: List<List<Int>>): IntArray {
        val res= mutableListOf<Int>()
        val iterListCount=nums.count()+nums.maxOf { it.size }-1
        
        for (i in 0..iterListCount){
            for ( j in 0..i){
                try {
                    res.add(nums[i-j][j])
                }catch (e:Exception){

                }

            }
        }

        println(res)
        return res.toIntArray()
    }
}

직접 더하는게 아닌,i+j를 해시맵에 담고 그걸 다 더해서 리턴?
Wrong Answer 55 / 56  

class Solution {
    fun findDiagonalOrder(nums: List<List<Int>>): IntArray {
        val res= mutableListOf<Int>()
        val numHashMap = hashMapOf<Int, MutableList<Int>>()

        for ((iIndex,i) in nums.withIndex()){
            for ((jIndex,j) in i.withIndex()){
                numHashMap[iIndex+jIndex]= (numHashMap[iIndex+jIndex]?.plus(j)?: mutableListOf(j)).toMutableList()
            }
        }
        for ((key,value) in numHashMap){
            val reversedValue = value.reversed()

            //println(reversedValue)
            res.addAll(reversedValue)

        }
        
        return res.toIntArray()
    }
}

시간복잡도는 해결했는데,
1
2
3
4 5 6 10 11 12 13 14 15 16
7
8
9

이런형태의 매우 긴 배열에서 문제가 나는데 직접 넣는정도 크기로는 재현이안됨

정답

class Solution {
    fun findDiagonalOrder(nums: List<List<Int>>): IntArray {
        val map = LinkedHashMap<Int, ArrayList<Int>>()
        val res = ArrayList<Int>()

        for (i in 0..nums.size - 1) {
            for (j in 0..nums[i].size - 1) {
                map.getOrPut(i + j, { ArrayList() }).add(nums[i][j])
            }
        }
        
        for (m in map.values) {
            res.addAll(m.reversed())
        }

        return res.toIntArray()
    }
}