'2025/05/02'에 해당되는 글 1건

Leetcode Problem:

• Push Dominoes

Summary

• This problem is about simulating the movement of dominoes in a line
• The dominoes can be pushed to the left or to the right, and they will move in the opposite direction if pushed from both sides.

Approach

• The approach used in the solution is to iterate through the dominoes and for each domino, check if it has been pushed to the left or to the right
• If it has been pushed to the left, all the dominoes to its left that have not been pushed will also be pushed to the left
• If it has been pushed to the right, all the dominoes to its right that have not been pushed will be pushed to the right
• If a domino has been pushed from both sides, it will stay still.

Complexity

• O(n)

Explanation

• The time complexity of the solution is O(n) because we are iterating through the dominoes once
• The space complexity is O(1) because we are not using any extra space that scales with the input size.

Solution Code:

class Solution {
public:
    string pushDominoes(string dominoes) {
        for(int i = 0 ; i < dominoes.size(); i++){
            if(dominoes[i] == 'L'){
                int j = i-1;
                while(j >= 0 && dominoes[j] == '.'){
                    dominoes.at(j) = 'L';
                    j--;
                }
            } else if(dominoes[i] == 'R'){
                int j = i+1;
                while(j < dominoes.size() && dominoes[j] == '.'){
                    j++;
                }
                if(j >= dominoes.size() || dominoes[j] == 'R'){
                    for(; i < j; i++){
                        dominoes.at(i) = 'R';
                    }
                    if(j < dominoes.size() && dominoes[j] == 'R'){
                        i--;
                    }
                } else{
                    int k = i + 1;
                    int l = j - 1;
                    while(k < l){
                        dominoes.at(k) = 'R';
                        dominoes.at(l) = 'L';
                        k++;
                        l--;
                    }
                    i = j;
                }
            }
        }
        return dominoes;
    }
};