Daily LeetCode Challenge - 1706. Where Will the Ball Fall

Problem From.

https://leetcode.com/problems/where-will-the-ball-fall/

오늘 문제는 matrix 의 제일 위쪽에 공을 넣었을때 경로를 따라 가다가 나오는 결과를 반환하는 문제였다.

각 공은 matrix 안의 숫자가 1 이면 오른쪽, -1 이면 왼쪽으로 이동하며, 벽에 부딫히거나 오른쪽과 왼쪽 길이 겹쳐서 더 이상 전진할 수 없으면 0을 반환한다.

풀이는 nested for loop 로 단순하게 구현하였다.

class Solution {
    fun findBall(grid: Array<IntArray>): IntArray {
        
        val length = grid.size
        val width = grid[0].size
        val answer = IntArray(width)
        
        loop1@ for(x in 0 until width) {
            
            var pos = x
            
            loop2@ for(y in 0..length) {
                
                if(y == length) {
                    break@loop2
                }
                
                if(grid[y][pos] == 1) {
                    if(pos + 1 == width || grid[y][pos + 1] == -1) {
                        pos = -1
                        break@loop2
                    }
                    pos += 1
                }else {
                    if(pos - 1 == -1 || grid[y][pos-1] == 1) {
                        pos = -1
                        break@loop2
                    }
                    pos -= 1
                }
            }
            
            answer[x] = pos
            
        }
        
        return answer
    }
}

위 풀이의 시간복잡도는 O(n^2) 가 된다.