[Leetcode] 838. Push Dominoes

문제

 

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

Push Dominoes - LeetCode

There are n dominoes in a line, and we place each domino vertically upright. In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left. Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

You are given a string dominoes representing the initial state where:

• dominoes[i] = 'L', if the ith domino has been pushed to the left,
• dominoes[i] = 'R', if the ith domino has been pushed to the right, and
• dominoes[i] = '.', if the ith domino has not been pushed.

Return a string representing the final state.

 

1. n개의 도미노가 주어지고, 각 도미노는 수직으로 세워져있고, 각 도미노는 동시에 왼쪽 또는 오른쪽으로 밀린다.

2. 왼쪽으로 쓰러지는 도미노는 왼쪽에 인접한 도미노를 밀어내고, 오른쪽으로 쓰러지는 도미노는 오른쪽에 인접한 도미노를 밀어낸다.

3. 양쪽으로 동시에 도미노가 쓰러질 때 힘의 균형으로 인해 수직인 도미노는 유지된다.

dominoes의 초기상태를 나타내는 문자열이 제공된다.

• dominoes[i] = 'L', 도미노가 왼쪽으로 밀릴 때
• dominoes[i] = 'R', 도미노가 오른쪽으로 밀릴 때
• dominoes[i] = '.', 도미노가 밀리지 않았을 때

 

Example 1:

Input	Output
dominoes = "RR.L"	"RR.L"
Explanation: The first domino expends no additional force on the second domino.

Example 2:

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

 

문제풀이 코드

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        dominoes = list(dominoes)
        right = -99
        i = 0
        
        while i < len(dominoes):
            if dominoes[i] == '.':
                i+=1
                continue
            elif dominoes[i] == 'L':
                if right < 0:
                    for j in range(i-1, -1, -1):
                        if dominoes[j] != '.':
                            break
                        else:
                            dominoes[j] = 'L'
                elif right >= 0 and right + 1 != i - 1 and right + 1 != i:
                    mid = ((i - right) // 2) + right
                    for j in range(right+1, mid+1 if (i-right) % 2 > 0 else mid):
                        dominoes[j] = 'R'
                    for j in range(mid+1, i):
                        dominoes[j] = 'L'
                right = -99
                i += 1
            elif dominoes[i] == 'R':
                if right >= 0:
                    for j in range(right+1, i+1):
                        dominoes[j] = 'R'
                right = i
                i+=1
        if right >= 0:
            for j in range(right+1, i):
                dominoes[j] = 'R'
                
        return ''.join(dominoes)

투포인터 방식으로 문제 접근

1. '.'을 만났을 때

  - i+1을 해준다.

2. 'L'을 만났을 때: right를 안만났을 때로 초기화하고, i + 1을 해준다

  - R을 만나지 않고 연속으로 L을 만났을 경우

      -> 현재 위치에서 하나씩 L로 바꾸면서 뒤로간다. '.'이 아닌 다른문자가 나오면 루프를 빠져나온다

  - 이전에 R이 존재했고, L을 만났을 경우

      -> 현재 R의 위치 + 1이 현재 L의 위치 - 1일 때, 현재 R의 위치 + 1이 i와 같을 때는 도미노가 쓰러지지 않는다

      -> R과 L은 동시에 쓰러지기 때문에 R과 L의 중간값을 구해서 R은 중간값 까지 'R'로 바꾸고 L은 중간값 + 1부터 현재 위치까지 'L'로 바꾼다

3. 'R'을 만났을 때: right를 현재위치로 초기화하고, i + 1을 해준다

  - L을 만나지 않고 연속으로 R을 만났을 경우

      -> 이전에 right값이 0보다 크고 현재위치가 아닐 때 R의 이전위치부터 현재위치까지 'R'로 바꿔준다

4. 루프를 빠져나오고 right값이 0보다 크면 right + 1부터 마지막까지 도미노를 오른쪽으로 'R'로 바꿔준다.

 

** 투포인터 방식으로 풀었지만 조건을 하나씩 다 처리하다보니 코드도 길어지고 가독성도 많이 떨어진거같음... 다음에 다시 보면서 줄일 수 있는건 줄이고 파이썬답게 풀어봐야겠다