새싹프로그래머의 이야기

777번: https://leetcode.com/problems/swap-adjacent-in-lr-string/

2337번: https://leetcode.com/problems/move-pieces-to-obtain-a-string/

문제: 'L' 과 'R' 이 포함된 두 문자열이 주어졌을 때, 문제에서 목표로 주어진 문자열을 만들 수 있는지 여부를 판별하는 문제

문제 설명:

두 문제 모두, 'L' 이라는 문자는 왼쪽으로만 이동 가능하며, 'R'이라는 문자는 오른쪽으로만 이동 가능하도록 되어있습니다.

이때 각 문자는 서로를 넘어갈 수 없습니다.

예를 들면, '_L_RR' 이라는 문자가 주어졌을 때, 'L__RR'은 만들 수 있지만 '__RLR'은 만들 수 없습니다.

풀이 코드:

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        if start.replace('_', '') != target.replace('_', ''):
            return False

        startL = [i for i in range(len(start)) if start[i] == 'L']
        startR = [i for i in range(len(start)) if start[i] == 'R']
        endL = [i for i in range(len(target)) if target[i] == 'L']
        endR = [i for i in range(len(target)) if target[i] == 'R']

        for i, j in zip(startL, endL):
            if i < j:
                return False

        for i, j in zip(startR, endR):
            if i > j:
                return False
        return True

풀이의 핵심은 두가지 입니다.

• 'L'과  'R'의 순서는 바뀔 수 없음
• 목표 문자열에서 기존 문자열 대비 'L'의 위치는 오른쪽에 존재할 수 없으며, 반대로 'R' 의 위치 또한 왼쪽에 존재 할 수 없다는 것입니다.

if start.replace('_', '') != target.replace('_', ''):
    return False

공백에 해당하는 문자열을 없앤 후, 두 문자열을 비교하여 순서를 확인합니다.

startL = [i for i in range(len(start)) if start[i] == 'L']
startR = [i for i in range(len(start)) if start[i] == 'R']
endL = [i for i in range(len(target)) if target[i] == 'L']
endR = [i for i in range(len(target)) if target[i] == 'R']

for i, j in zip(startL, endL):
    if i < j:
        return False

for i, j in zip(startR, endR):
    if i > j:
        return False

위 코드를 통해, 'L'과 'R'의 위치 변화를 판별합니다.

*풀이는 Discuss에서 투표를 많이 받은 풀이를 참조하였습니다.