[LeetCode] 838. Push Dominoes

문제

'L', 'R', '.'로 된 문자열이 주어집니다. 넘어진 도미노는 1초마다 옆 도미노를 같은 방향으로 넘어뜨립니다. 양쪽에서 동시에 밀리는 도미노는 그대로 서 있습니다. 최종 상태를 구하는 문제입니다.

아이디어: 힘을 누적한다

각 칸이 오른쪽으로 받는 힘과 왼쪽으로 받는 힘을 따로 구해서 합칩니다.

• R에서 멀어질수록 오른쪽 힘이 1씩 약해집니다.
• L에서 멀어질수록 왼쪽 힘이 1씩 약해집니다.
• 합이 양수면 R, 음수면 L, 0이면 .입니다.

가까운 쪽 힘이 더 크기 때문에 먼저 도착하는 쪽이 이긴다는 규칙이 그대로 표현됩니다. 거리가 같으면 합이 0이 되어 서 있게 됩니다.

풀이

function pushDominoes(dominoes: string): string {
    const n = dominoes.length
    const force = Array(n).fill(0);

    // 왼 → 오: R 의 힘
    let f = 0;
    for (let i = 0; i < n; i++) {
        if (dominoes[i] === 'R') f = n;
        else if (dominoes[i] === 'L') f = 0;
        else f = Math.max(f - 1, 0);
        force[i] += f;
    }

    // 오 → 왼: L 의 힘
    f = 0;
    for (let i = n - 1; i >= 0; i--) {
        if (dominoes[i] === 'L') f = n;
        else if (dominoes[i] === 'R') f = 0;
        else f = Math.max(f - 1, 0);
        force[i] -= f;
    }

    return force.map(f => {
        if (f >= 1) return 'R';
        if (f < 0) return 'L';
        return '.';
    }).join('');
};

포인트

• 시작 힘을 n으로 두는 이유: 거리는 최대 n - 1이므로, 힘이 0으로 떨어지기 전에 문자열 끝까지 닿습니다.
• 반대 방향 도미노를 만나면 0으로 리셋: 오른쪽으로 가다가 L을 만나면 그 너머로는 R의 힘이 전달되지 않습니다.
• 예시 R...L: 오른쪽 힘 [5,4,3,2,0], 왼쪽 힘 [0,2,3,4,5], 합 [5,2,0,-2,-5], 결과 RR.LL

복잡도

• 시간 O(n): 두 번 순회합니다.
• 공간 O(n): force 배열을 씁니다.