[LeetCode][Kotlin] 838. Push Dominoes

838. Push Dominoes

There are n dominoes in a line, and we place each domino vertically upright. In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

 

After each second, each domino that is falling to the left pushes the adjacent domino on the left. Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

 

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

 

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

 

You are given a string dominoes representing the initial state where:

• dominoes[i] = 'L', if the ith domino has been pushed to the left,
• dominoes[i] = 'R', if the ith domino has been pushed to the right, and
• dominoes[i] = '.', if the ith domino has not been pushed.

Return a string representing the final state.

한 줄에 n개의 도미노가 있고, 각 도미노를 수직으로 세워 놓습니다. 처음에는 도미노 몇 개를 왼쪽이나 오른쪽으로 동시에 밀어냅니다. 

매초마다 왼쪽으로 떨어지는 각 도미노는 왼쪽에 있는 인접한 도미노를 밀어냅니다. 마찬가지로, 오른쪽으로 떨어지는 도미노는 오른쪽에 있는 인접한 도미노를 밀어냅니다. 

수직 도미노는 양쪽에서 도미노가 떨어지면 힘의 균형으로 인해 가만히 있습니다. 

이 질문의 목적을 위해, 우리는 떨어지는 도미노가 떨어지거나 이미 떨어진 도미노에 추가 힘을 소비하지 않는다는 점을 고려할 것입니다. 

초기 상태를 나타내는 문자열 도미노가 제공됩니다. 
- dominoes[i] = 'L', i번째 도미노가 왼쪽으로 밀린 경우, 
- dominoes[i] = 'R', i번째 도미노가 오른쪽으로 밀린 경우 
- dominoes[i] = '.', i번째 도미노가 푸시되지 않은 경우. 

최종 상태를 나타내는 문자열을 반환합니다.

 

Example 1:

Input: dominoes = "RR.L"

Output: "RR.L"

Explanation: The first domino expends no additional force on the second domino.

 

Example 2:

Input: dominoes = ".L.R...LR..L.."

Output: "LL.RR.LLRRLL.."

 

Constraints:

• n == dominoes.length
• 1 <= n <= 10^5
• dominoes[i] is either 'L', 'R', or '.'.

---

코드

class Solution {
    fun pushDominoes(dominoes: String): String {
        val dom = dominoes.toMutableList()
        
        val q = ArrayDeque<Pair<Int, Char>>()
        dominoes.forEachIndexed { i, v ->
            if (v != '.') {
                q.add(i to v)
            }
        }

        while (q.isNotEmpty()) {
            val (i, v) = q.removeFirst()

            if (v == 'L' && i > 0 && dom[i - 1] == '.') {
                dom[i - 1] = 'L'
                q.add(i - 1 to 'L')
            } else if (v == 'R') {
                if (i + 1 < dom.size && dom[i + 1] == '.') {
                    if (i + 2 < dom.size && dom[i + 2] == 'L') {
                        q.removeFirst()
                    } else {
                        dom[i + 1] = 'R'
                        q.add(i + 1 to 'R')
                    }
                }
            }
        }

        return dom.joinToString("")
    }
}