838 - Push Dominoes

info

• 문제 보기: 838 - Push Dominoes
• 소요 시간: 33분 48초
• 풀이 언어: java
• 체감 난이도: 2️⃣~3️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

투포인터

풀이 코드

info

• 메모리: 46300 KB
• 시간: 18 ms

class Solution {
    int[] rdist;
    int[] ldist;
    int n;

    public String pushDominoes(String dominoes) {
        n = dominoes.length();
        char[] dArr = dominoes.toCharArray();
        rdist = new int[n];
        ldist = new int[n];
        
        int force = 0;
        for (int i = 0; i < n; ++i) {
            if (dArr[i] == 'R') {
                force = 1;
                rdist[i] = force++;
            }
            else if (dArr[i] == 'L') {
                rdist[i] = 0;
                force = 0;
            }
            else {
                if (force > 0) rdist[i] = force++;
                else rdist[i] = 0;
            }
        }

        force = 0;
        for (int i = n-1; i > -1; --i) {
            if (dArr[i] == 'L') {
                force = 1;
                ldist[i] = force++;
            }
            else if (dArr[i] == 'R') {
                ldist[i] = 0;
                force = 0;
            }
            else {
                if (force > 0) ldist[i] = force++;
                else ldist[i] = 0;
            }
        }

        for (int i = 0; i < n; ++i) {
            if (dArr[i] == '.') {
                if (ldist[i] < rdist[i]) dArr[i] = ldist[i] > 0 ? 'L' : 'R';
                else if (ldist[i] > rdist[i]) dArr[i] = rdist[i] > 0 ? 'R' : 'L';
            }
        }

        return String.valueOf(dArr);
    }
}

풀이 해설

시간복잡도를 살짝만 포기하면 $T(3n)$ 막구현으로 풀리는 문제이다.

도미노가 넘어지는 형상을 몇 개 그려보면, L과 R이 맞닿는 부분은 반드시 힘이 경합됨을 알 수 있다.

이는 L과 R 사이에 .이 홀수개이든 짝수개이든 동일하게 적용돼서, R 힘이 더 쎄서 L이었던게 R로 바뀌고 그런 경우가 없다.

if (dArr[i] == '.') {
    if (ldist[i] < rdist[i]) dArr[i] = ldist[i] > 0 ? 'L' : 'R';
    else if (ldist[i] > rdist[i]) dArr[i] = rdist[i] > 0 ? 'R' : 'L';
}

그래서 distance 기반으로 비교해주고 (더 가까운 쪽을 선택)

distance를 0과 양수 상태로 분리해서

한쪽에 L 또는 R이 없는(= distance가 0인) corner case만 고려해주면 된다.

메모

• 풀이 시간 생각하면 투포인터 써주기엔 아까운듯.