[LeetCode] 838. Push Dominoes

https://leetcode.com/problems/push-dominoes/

Push Dominoes - LeetCode

Push Dominoes.

 

도미노를 어느방향으로 밀지 주어지고, 이대로 밀었을 때 도미노의 모습이 어떻게 될지 출력하는 문제다.

이때 왼쪽에서 민 거리와 오른쪽에서 민 거리가 같을 경우엔 넘어지지 않는다.

 

바로 위 도미노 그림에서 두번째 주황색 도미노를 보면,

두칸 왼쪽에서 도미노가 오른쪽으로 넘어지고 두칸 오른쪽에서 도미노가 왼쪽으로 넘어진다.

양쪽이 같은 거리에서 넘어지므로 이 도미노는 넘어지지 않는다.

 

반면에, 그 바로 오른쪽 상황을 보면

똑같이 왼쪽 두개가 넘어지고 오른쪽 두개가 넘어졌지만 안넘어진 도미노는 없다.

이유는 

 

여기서 가장 왼쪽 도미노를 보면 왼쪽에서 넘어온 도미노의 거리는 0, 오른쪽에서 넘어온 도미노의 거리는 3이다.

두번째 도미노는 왼쪽 거리 1, 오른쪽 거리는 2다.

세번째는 왼쪽 2, 오른쪽은 1이다.

마지막은 왼쪽 3, 오른쪽이 0이다.

 

따라서 하나하나를 살펴보면 양쪽에서 같은 거리에서 넘어오지 않아 한쪽으로 치우치게 된 것이다.

 

위 예시를 보면 풀이방법을 알 수 있다.

index를 하나 잡아 그 위치 기준으로 가장 가까운 왼쪽에서 넘어온 도미노와 오른쪽에서 넘어온 도미노의 거리를 살펴보면 된다.

 

이 때 우리는 거리를 점수 개념으로 바꿔 가까울 수록 이 점수를 크게 또는 낮게 만들어줘야 한다.

왼쪽에서 넘어온 도미노의 점수는 +로, 오른쪽에서 넘어온 도미노는 -로 나타내자.

최대점수는 어떻게 될까? 문제조건에서 도미노의 최대길이는 100000이라고 한다.

고로 +100000, -100000으로 잡아주자.

또는 좀더 compact 하게 하고 싶은 분들은 주어진 domino의 사이즈로 잡아줘도 된다.

어차피 int 형의 범위를 초과하지 않아 상관은 없다.

멀어질수록 절대값이 감소하게 해주자.

 

위의 그림만 본다면

 

첫번째 도미노 : 왼쪽 0, 오른쪽 3 이므로 왼쪽은 +100000-0 = +100000점, 오른쪽은 -100000+3 = -99997점

두번째 도미노 : 왼쪽 1, 오른쪽 2 이므로 왼쪽은 +100000-1 = +99999점, 오른쪽은 -100000+2 = -99998점

세번째 도미노 : 왼쪽 2, 오른쪽 1 이므로 왼쪽은 +100000-2 = +99998점, 오른쪽은 -100000+1 = -99999점

네번째 도미노 : 왼쪽 3, 오른쪽 0 이므로 왼쪽은 +100000-3 = +99997점, 오른쪽은 -100000+0 = -100000점

 

전체 점수를 환산하면

 

첫번째 : 100000-99997 = +3

두번째 : 99999-99998 = +1

세번째 : 99998-99999 = -1

네번째 : 99997-100000 = -3

 

이 점수가 양수면 오른쪽으로 넘어지고, 음수면 왼쪽으로 넘어진다.

따라서 이 도미노의 결과는 RRLL이 된다.

 

이제 이를 코드로 작성해보자.

왼쪽에서 오른쪽으로 넘어지는 도미노의 점수를 나타내는 배열(R)과 오른쪽에서 왼쪽으로 넘어지는 도미노의 점수를 나타내는 배열(L)을 생성해준다.

또 결과를 나타낼 string을 만들어준다.

int L[100000], R[100000];
string ret="";

이제 도미노의 사이즈대로 index를 쭉 훑으며 점수를 계산해준다.

왼쪽에서 오른쪽으로 갈때와 오른쪽에서 왼쪽으로 갈때를 따로 계산을 해주어야한다.

 

왼쪽에서 오른쪽으로 갈때는 

1. 오른쪽으로 밀릴때

2. 왼쪽으로 밀릴때

3. 안 밀릴때

로 구분을 해준다.

 

1. 오른쪽으로 밀릴 경우, 오른쪽으로 밀린 거리가 0이므로 최대점수로 세팅해준다.

2. 왼쪽으로 밀릴 경우, 오른쪽으로 미는 점수만 계산하므로 0점으로 세팅해준다.

3. 안 밀린다면, 왼쪽 도미노의 점수를 봐준다. 왼쪽도미노가 +라면 이는 밀리고 있는 도미노이므로 이 도미노의 점수에서 1감소시켜 저장해주고, 왼쪽도미노가 0이라면 미는 도미노가 없으므로 0점으로 세팅한다.

 

오른쪽에서 왼쪽으로 갈때는 반대로 해주면 된다.

for (int i=0; i<dominoes.size(); i++) {
	if (dominoes[i]=='R') R[i] = 100000;
	else if (dominoes[i]=='.' && i>0 && R[i-1]>0) R[i] = R[i-1]-1;
	else R[i] = 0;
	int r = dominoes.size()-1-i;
	if (dominoes[r]=='L') L[r] = -100000;
	else if (dominoes[r]=='.' && r<dominoes.size()-1 && L[r+1]<0) L[r] = L[r+1]+1;
	else L[r] = 0;
}

마지막으로 다시 한번 훑어주며 L과 R을 살펴보고 둘의 점수를 더해 +면 R, -면 L, 0이면 .을 ret에 추가해주면 된다.

 

for (int i=0; i<dominoes.size(); i++) ret+=R[i]+L[i]>0?"R":R[i]+L[i]<0?"L":".";

 

전체 코드는 아래와 같다.

 

class Solution {
public:
    int L[100000], R[100000];
    string ret="";
    string pushDominoes(string dominoes) {
        for (int i=0; i<dominoes.size(); i++) {
            if (dominoes[i]=='R') R[i] = 100000;
            else if (dominoes[i]=='.' && i>0 && R[i-1]>0) R[i] = R[i-1]-1;
            else R[i] = 0;
            int r = dominoes.size()-1-i;
            if (dominoes[r]=='L') L[r] = -100000;
            else if (dominoes[r]=='.' && r<dominoes.size()-1 && L[r+1]<0) L[r] = L[r+1]+1;
            else L[r] = 0;
        }
        for (int i=0; i<dominoes.size(); i++) ret+=R[i]+L[i]>0?"R":R[i]+L[i]<0?"L":".";
        return ret;
    }
};