838. Push Dominoes

https://leetcode.com/problems/push-dominoes/?envType=daily-question&envId=2025-05-01

주어진 도미노 배열 문자열에서 '.'(무너지지 않은 도미노)에 양옆에서 밀리는 힘('L', 'R')이 작용하면, 이 도미노가 어느 방향으로 쓰러질지 구하는 문제

• 입력: dominoes: str
  • 길이 n인 문자열, 각 문자는 '.', 'L', 'R' 중 하나
• 출력: 최종 상태 문자열 ('.', 'L', 'R' 조합)

---

📋 알고리즘 개요

1. 현재 상태(cur)를 list로 관리
2. 반복: 한 번의 라운드에서 쓰러질 도미노를 계산해서 새 배열(new)에 기록
3. 더 이상 쓰러질 도미노가 없으면 반복 종료
4. 각 라운드가 끝나면 cur = new
5. 최종 cur를 문자열로 합쳐서 반환

---

💡 핵심 아이디어

• 동시성 유지: 한 라운드 안에서 일어난 변화는 다음 라운드에만 반영되도록, cur와 new를 분리
• 양방향 힘 계산:
  • 왼쪽에서 밀리는 힘 LeftForce → 바로 오른쪽 이웃(i+1)이 'L'
  • 오른쪽에서 밀리는 힘 RightForce → 바로 왼쪽 이웃(i-1)이 'R'
  • 두 힘이 동시에 오면 무시(. 유지)
• 반복 종료 조건: 한 라운드에서 쓰러진 도미노가 없다면(changed == False)

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        cur = list(dominoes)
        while True:
            new = cur.copy()
            changed = False

            for i in range(n):
                # 이미쓰러진 벽돌
                if cur[i] != '.':
                    continue
                # L방향 힘이 있으려면 i+1 벽돌이 있고 그 벽돌이 L 이여햐 함
                LeftForce = (i < n-1   and cur[i+1] == 'L')
                # R방향 힘이 있으려면 i-1 벽돌이 있고 그 벽돌이 R 이여햐 함
                RighForce = (i > 0  and cur[i-1] == 'R')

                if LeftForce and not RighForce:
                    new[i] = 'L'
                    changed = True
                elif RighForce and not LeftForce :
                    new[i] = 'R'
                    changed = True
            if changed == False:
                break
            cur = new
        return ''.join(cur)