[LeetCode] 838. Push Dominoes

문제 출처: https://leetcode.com/problems/push-dominoes/

Push Dominoes - LeetCode

 

문제

n 개의 도미노가 한 줄에 일렬로 세워져있다. 세워진 도미노의 일부를 왼쪽 혹은 오른쪽으로 동시에 쓰러트린다.

 

왼쪽으로 쓰러트렸다면 인접한 왼쪽의 도미노를 연쇄적으로 쓰러트린다. 이와 유사하게, 오른쪽으로 쓰러트렸다면 인접한 오른쪽 도미노를 연쇄적으로 쓰러트린다.

 

수직으로 세워진 도미노의 양쪽에서 힘이 가해진다면, 힘의 균형으로 인해 쓰러지지 않는다.

 

이 문제의 목적을 위해, 쓰러진 혹은 쓰러지고 있는 도미노에 어떠한 추가 힘도 가하지 않는다.

 

다음과 같이 초기 상태가 표현되어 있는 문자열 dominoes 가 주어진다:

• dominoes[i] = 'L', ith 도미노에 왼쪽으로 힘이 가해짐
• dominoes[i] = 'R', ith 도미노에 오른쪽으로 힘이 가해짐
• dominoes[i] = '.', ith 도미노에 힘이 가해지지 않음

마지막 상태를 표현하고 있는 문자열 a를 반환하라.

 

예제

Input: dominoes = "RR.L"
Output: "RR.L"

Explanation: The first domino expends no additional force on the second domino.

Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

 

풀이

문제의 답을 내놓기 위해서 주의해야 되는 부분에 대해 생각해보면, 양쪽에서 힘을 받아 균형을 유지하는 도미노가 무엇인가 이다. 만약 양쪽으로 힘을 받는 도미노가 없다라고 한다면, 힘을 받는 방향대로만 표시하면 될 것이기 때문이다.

 

양쪽에서 힘을 받는다는 의미는 자기 자신(dominos[i])을 기준으로 왼쪽 도미노가 오른쪽으로 쓰러지고 있고, 오른쪽 도미노가 왼쪽으로 쓰러지고 있다는 이야기이다.

 

우선, 초기에 힘이 가해지고 있는 도미노의 위치를 파악할 필요가 있다. 이를 기준으로 각 도미노가 어디로 쓰러질지 예상할 것이다.

 

힘이 가해지는 도미노의 위치를 저장하고 있는 배열이 indexes라 할때 다음의 두 관계를 생각할 수 있다.

• indexes[i] == 'L' 이고 indexes[i+1] == 'R' 이라면, 서로 영향을 끼치지 않음
• indexes[i] == 'R' 이고 indexes[i+1] == 'L' 이라면, 서로 영향을 끼쳐 중간에 균형을 유지하는 도미노가 존재할 수 있음

이 사실을 기반으로 아래와 같이 코드 틀을 만들어 볼 수 있다.

var pushDominoes = function(dominoes) {
    let ans = '';
    
    // 초기 힘이 가해진 도미노의 위치를 기록
    const indexes = [];
    dominoes.split('').forEach((force, idx) => {
    	if (force != '.') indexes.push(idx);
    });
    
    const ansList = Array(dominoes.length).fill('.');
    
    // indexes를 기준으로 케이스 분리
    for (let i = 0; i < indexes.length; i++) {
    	const curIdx = indexes[i];
        const nextIdx = i + 1 < indexes.length ? indexes[i+1] : null;
        
        const cur = dominoes[curIdx];
        const next = nextIdx ? dominoes[nextIdx] ? null;
        
        ansList[curIdx] = cur;
        
        if (cur == 'R' && next == 'L') {
        	// Do Something
        } else if (cur == 'R') {
        	// Do Something
        } else {
        	// Do Something
        }
    }
    
    return ans = ansList.join('');
}

먼저 한쪽 방향으로 쓰러지는 도미노를 생각해보자.

 

만약, 왼쪽('L')으로 힘이 가해지고 있다면 최초 힘이 가해진 위치에서 왼쪽 도미노들이 영향을 받을 것이다. 마찬가지로 오른쪽('R')으로 힘이 가해지고 있다면 최초 힘이 가해진 위치에서 오른쪽 도미노들이 영향을 받을 것이다.

 

그렇다면, 이러한 영향이 어디까지 이어질 것인가를 생각해봐야 하는데, 별도로 힘이 가해지지 않았다면 현재 발생된 힘의 영향을 그대로 받을 것이다. 이를 코드로 작성하면 아래와 같다.

var pushDominoes = function(dominoes) {
    let ans = '';
    
    // 초기 힘이 가해진 도미노의 위치를 기록
    const indexes = [];
    dominoes.split('').forEach((force, idx) => {
    	if (force != '.') indexes.push(idx);
    });
    
    const ansList = Array(dominoes.length).fill('.');
    
    // indexes를 기준으로 케이스 분리
    for (let i = 0; i < indexes.length; i++) {
    	const curIdx = indexes[i];
        const nextIdx = i + 1 < indexes.length ? indexes[i+1] : null;
        
        const cur = dominoes[curIdx];
        const next = nextIdx ? dominoes[nextIdx] : null;
        
        ansList[curIdx] = cur;
        
        if (cur == 'R' && next == 'L') {
        	// Do Something
        } else if (cur == 'R') {
            let j = curIdx + 1;
            while (j < dominoes.length && dominoes[j] == '.') {
            	ansList[j] = 'R';
                j += 1;
            }
        } else if (cur == 'L') {
            let j = curIdx - 1;
            while (j >= 0 && dominoes[j] == '.') {
            	ansList[j] = 'L';
                j -= 1;
            }
        }
    }
    
    return ans = ansList.join('');
}

양쪽에서 힘을 받는 경우를 생각해보자.

 

양쪽에서 힘이 가해지는 경우, 힘이 부딪히는 위치는 중앙 부분이 될 것이다. 중앙 부분의 양 사이드에서는 중앙 부분을 향해 넘어지는 그림이 될 것이기 때문에 이를 고려하여 코드를 구현하면 다음과 같다.

var pushDominoes = function(dominoes) {
    let ans = '';
    
    // 초기 힘이 가해진 도미노의 위치를 기록
    const indexes = [];
    dominoes.split('').forEach((force, idx) => {
    	if (force != '.') indexes.push(idx);
    });
    
    const ansList = Array(dominoes.length);
    
    // indexes를 기준으로 케이스 분리
    for (let i = 0; i < indexes.length; i++) {
    	const curIdx = indexes[i];
        const nextIdx = i + 1 < indexes.length ? indexes[i+1] : null;
        
        const cur = dominoes[curIdx];
        const next = nextIdx ? dominoes[nextIdx] ? null;
        
        ansList[curIdx] = cur;
        
        if (cur == 'R' && next == 'L') {
        	ansList[nextIdx] = next;
            for (let j = curIdx+1, k = nextIdx-1; j < k; j++, k--) {
            	ansList[j] = 'R';
                ansList[k] = 'L';
            }
            // i + 1까지 한번에 처리했기 때문에 i를 증가시켜줘야 함
            i += 1;
        } else if (cur == 'R') {
            let j = curIdx + 1;
            while (j < dominoes.length && dominoes[j] == '.') {
            	ansList[j] = 'R';
                j += 1;
            }
        } else if (cur == 'L') {
            let j = curIdx - 1;
            while (j >= 0 && dominoes[j] == '.') {
            	ansList[j] = 'L';
                j -= 1;
            }
        }
    }
    
    return ans = ansList.join('');
}

지금까지의 풀이는 서로 영향을 끼치는 도미노끼리 분리하고 쓰러트리는 과정을 시뮬레이션했다고 할 수 있다.

 

이러한 방법 이외에 도미노에 가해지는 영향력을 계산하는 방법이 있다.

 

도미노의 총 길이가 N이라 할 때, 임의의 위치 i 에 힘이 가해졌다면 그 위치에서 N의 힘이 가해졌다고 하고, 그리고 힘의 방향대로 도미노가 쓰러지면서 그 힘이 1씩 감소한다고 생각해보자.

 

현재 도미노에 2가지 힘('R', 'L')이 가해지고, 이 힘은 서로 충돌하는 힘이기 때문에 이를 구분하기 위해서 'L'의 영향력에는 -1을 곱하여 그 영향력을 표시하도록 하자. 예를 들어, dominoes = ".L.R...LR..L.." 이라하면, 아래와 같이 L과 R이 영향력을 구할 수 있다.

	.	L	.	R	.	.	.	L	R	.	.	L	.	.
L	-11	-12	0	0	-9	-10	-11	-12	0	-10	-11	-12	0	0
R	0	0	0	12	11	10	9	0	12	11	10	0	0	0

위의 표를 자세히 보면 알 수 있겠지만, 충돌하는 힘이 발생된 지점에서는 그 영향력을 0로 만들어주는 것에 주의해야 한다.

 

표에 표시된 영향력을 하나로 합치면 아래와 같이 표현될 수 있는데, 합쳐진 영향력이 0보다 크다면 'R', 작다면 'L' 그리고 0과 같다면 '.' 을 표시하는 것으로 최종 답을 구할 수 있다.

	.	L	.	R	.	.	.	L	R	.	.	L	.	.
L	-11	-12	0	0	-9	-10	-11	-12	0	-10	-11	-12	0	0
R	0	0	0	12	11	10	9	0	12	11	10	0	0	0
Sum	-11	-12	0	12	2	0	-2	-12	12	1	-1	-12	0	0
result	L	L	.	R	R	.	L	L	R	R	L	L	.	.

이러한 방식을 코드로 작성하면 아래와 같다.

var pushDominoes_calcForce = function(dominoes) {
    const N = dominoes.length;
    const LForces = Array(N);
    const RForces = Array(N);
    
    let force = dominoes[N-1] == 'L' ? (-1 * N) : 0;
    for (let i = N-1; i >= 0; i--) {
        if (dominoes[i] == 'L') {
            force = (-1 * N);
        } else if (dominoes[i] == 'R') {
            force = 0;
        }
        LForces[i] = force;
        force = Math.min(0, force + 1);
    }
    
    force = dominoes[0] == 'R' ? N : 0;
    for (let i = 0; i < N; i++) {
        if (dominoes[i] == 'R') {
            force = N;
        } else if (dominoes[i] == 'L') {
            force = 0;
        }
        RForces[i] = force;
        force = Math.max(0, force - 1);
    }
    
    let ans = '';
    for (let i = 0; i < N; i++) {
        const sum = LForces[i] + RForces[i];
        if (sum > 0) { ans += 'R'; }
        else if (sum < 0) { ans += 'L'; }
        else { ans += '.'; }
    }
    return ans;
};

 

 

 

Github: 838.js

GitHub - opwe37/Algorithm-Study