[LeetCode] 2337. Move Pieces to Obtain a String (Python)

 

난이도: Medium

문제 설명

---

You are given two strings start and target, both of length n. Each string consists only of the characters 'L', 'R', and '_' where:

• The characters 'L' and 'R' represent pieces, where a piece 'L' can move to the left only if there is a blank space directly to its left, and a piece 'R' can move to the right only if there is a blank space directly to its right.
• The character '_' represents a blank space that can be occupied by any of the 'L' or 'R' pieces.

Return true if it is possible to obtain the string target by moving the pieces of the string start any number of times. Otherwise, return false.

 

문제 예제

---

Example 1:

Input: start = "_L__R__R_", target = "L______RR"
Output: true
Explanation: We can obtain the string target from start by doing the following moves:
- Move the first piece one step to the left, start becomes equal to "L___R__R_".
- Move the last piece one step to the right, start becomes equal to "L___R___R".
- Move the second piece three steps to the right, start becomes equal to "L______RR".
Since it is possible to get the string target from start, we return true.

Example 2:

Input: start = "R_L_", target = "__LR"
Output: false
Explanation: The 'R' piece in the string start can move one step to the right to obtain "_RL_".
After that, no pieces can move anymore, so it is impossible to obtain the string target from start.

Example 3:

Input: start = "_R", target = "R_"
Output: false
Explanation: The piece in the string start can move only to the right, so it is impossible to obtain the string target from start.

 

 

제한 사항

---

• n == start.length == target.length
• 1 <= n <= 10^5
• start and target consist of the characters 'L', 'R', and '_'.

 

✏️ Solution(솔루션)

---

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        if start.count('_') != target.count('_'):
            return False
            
        n = len(start)
        j = 0

        for i in range(n):
            if target[i] == '_':
                continue
            while start[j] == '_':
                j+=1

            if start[j] != target[i]:
                return False
            elif start[j] == 'R' and target[i] == 'R' and j > i:
                return False
            elif start[j] == 'L' and target[i] == 'L' and j < i:
                return False
            else:
                j+=1

        return True

 

일단 start의 '_' 갯수와 target의 '_'의 갯수가 다르면 False를 return하게 하고 코드를 짜기 시작했다.

서로의 '_' 갯수가 다르면 어떻게 해도 target에 맞게 바꿀 수 없기 때문이다.

 

'_'의 갯수가 같은 경우에는 투포인터 알고리즘을 사용하여 target으로 변환이 가능한지 확인하였다.

 

코드에서 i는 target의 현재 문자('L' or 'R') 위치를, j는 start의 현재 문자 위치를 가리킨다.

이 때, target에서 '_'는 무시하고 넘어가고, start에서도 '_'는 무시하며 j를 증가시켜 다음 문자를 찾는다.

 

그러다 start[j], target[i] 모두 문자를 가리키면 두 문자를 비교한다.

일단, start[j] 와 target[i]가 서로 다른 문자라면 False를 반환한다. 이런 경우에는 어떻게 해도 변환할 수 없기 때문이다.

(ex) start: _LR_, target: R_L_   ==>  False)

 

또한, start[j]와 target[i]가 'R'로 같지만 j가 i보다 크면 False를 반환한다. R은 오른쪽으로 밖에 갈 수 없기 때문에 j가 i 보다 커야 변환할 수 있기 때문이다.

(ex) start: _R, target: R_  ==>  False)

 

마찬가지로 start[j]와 target[i]가 'L'로 같지만 j가 i보다 작으면 False를 반환한다. L은 왼쪽으로 밖에 갈 수 없기 때문에 j가 i보다 작아야 변환할 수 있기 때문이다.

(ex) start: "L_", target: "_L"  ==>  False)

 

만약 이런 경우의 해당이 되지 않는다면 다시 i와 j를 증가시키며 연산을 진행한다.

 

그러다 반복문을 빠져나오면 변환이 가능하다고 판단해 True를 return하고 정답을 맞출 수 있었다.

---

2337. Move Pieces to Obtain a String