Push Dominoes

838. Push Dominoes

class Solution {
public:
    string pushDominoes(string dominoes) {
        queue<int> q;
        int len = dominoes.size();
        for (int i = 0; i < len; ++i) {
            if (dominoes[i] != '.') {
                q.push(i);
            }
        }

        while (!q.empty()) {
            int i = q.front();
            q.pop();
            int nn = 1;
            if (dominoes[i] == 'L') {
                nn = -1;
            }
            int ni = i + nn;
            if (0 <= ni && ni < len && dominoes[i + nn] == '.') {
                if (dominoes[i] == 'R' && q.front() == ni + 1 && dominoes[ni + 1] == 'L') {
                    q.pop();
                    continue;
                }
                dominoes[ni] = dominoes[i];
                q.push(ni);
            }
        }
        return dominoes;
    }
};

넘어뜨린 도미노 왼쪽부터 오른쪽 순으로 시뮬레이션.
다음 넘어질 곳이 서있을때 이어서 넘어질수 있다.
왼쪽에서 오른쪽으로 처리하는 특성상 R 일때 다음 처리할 도미노가 L 이고, 그 L 위치가 현재 R 의 다음다음일때, L, R 두 도미노가 동시에 넘어지면 가운데 도미노는 서있어야 하므로 현재 R 과 다음 L 을 처리 하지 않는디.
이 외에는 진행방향의 다음 도미노를 넘어뜨리고 다음 도미노 위치를 큐에 넣어 큐가 빌때 까지 시뮬레이션을 계속 한다.

Time: O(n)

• 모든 도미노를 시뮬레이션 하므로 n

Space: O(n)

• queue 최대 값 n
• 큐를 안쓰고 O(1) 로도 풀수는 있을듯.