리트코드 2337. Move Pieces to Obtain a String (Python3, Medium) - 인덱스와 직관 활용!

문제 링크 : https://leetcode.com/problems/move-pieces-to-obtain-a-string/

 

문제 설명 :  

 

start라는 string에서, "L"은 왼쪽으로, "R"은 오른쪽으로 이동할 수 있습니다.

start에서 target으로 이동할 수 있는지를 False, True를 통해서 return 하세요.

 

예시)

1. input :

start = "_L__R__R_", target = "L______RR"

output: True

 

2. input:

start = "R_L_", target = "__LR"

output: False

3. input:

start = "_R", target = "R_"

output: False

 

접근방법 : 처음에는 start 스트링을 수정하거나, 리스트로 바꿔서 하려고 했었는데,

while 이나 for loop를 돌면서 그 안에서 pop 하는 방법이 굉장히 어렵다는 것을 깨달았습니다.

Time Limit Exceeded 가 걸리기는 했지만, 8개의 test case를 통과한 솔루션을 작성하기는 하였습니다.

새로 리스트를 두 개를 만들어서, "_"언더스코어를 제외한 값들을 넣어주고, 

두 개를 비교하는 방법을 사용하면서, 인덱스를 같이 넣어주면서 start의 index와 target의 index를 비교하면 valid 여부를 쉽게 판단할 수 있습니다.

 

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        n = len(start)
        s_list, t_list = [], []
        
        for i in range(n):
            if start[i] != "_":
                s_list.append((start[i], i))
            
            if target[i] != "_":
                t_list.append((target[i], i))
        
        if len(s_list) != len(t_list):
            return False
        
        for i in range(len(s_list)):
            if s_list[i][0] != t_list[i][0]:
                return False
            elif s_list[i][0] == "L" and s_list[i][1] < t_list[i][1]:
                return False
            elif s_list[i][0] == "R" and s_list[i][1] > t_list[i][1]:
                return False
        
        return True

 

아래는 삽질의 결과...

 

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        n = len(start)
        start_l, start_r = [0] * n, [0] * n
        target_l, target_r = [0] * n, [0] * n
        result_l, result_r = [0] * n, [0] * n

        
        for i in range(n):
            if start[i] == "L":
                start_l[i] = 1
            if start[i] == "R":
                start_r[i] = 1
            if target[i] == "L":
                target_l[i] = 1
                result_l[i] = 1
            if target[i] == "R":
                target_r[i] = 1
                result_r[i] = 1
        
        if not (sum(start_l) == sum(target_l) and sum(start_r) == sum(target_r)):
            return False
        
        l_count, r_count = sum(start_l), sum(start_r)
        
        for i in range(n):
            if start_l[i] == 1:
                target_i = i
                while target_i >= 0 and (result_l[target_i] != 1 and target_r[target_i] != 1):
                    if (result_l[target_i] == 1 or target_r[target_i] == 1):
                        break
                    target_i -= 1
                # print(i, target_i)

                if target_i >= 0 and result_l[target_i] == 1:
                    # target_l[target_i] -= 1
                    # start_l[i] -= 1
                    result_l[target_i] -= 1
        
        for i in range(n-1, -1, -1):
            if start_r[i] == 1:
                target_i = i
                while target_i < n and (result_r[target_i] != 1 and target_l[target_i] != 1):
                    if (result_r[target_i] == 1 or target_l[target_i] == 1):
                        break
                    target_i += 1
                if target_i < n and result_r[target_i] == 1:
                    # target_r[target_i] -= 1
                    # start_r[i] -= 1
                    result_r[target_i] -= 1
        # print(start_l, start_r, target_l, target_r)
        # print(result_l, result_r)
        if sum(result_l) == 0 and sum(result_r) == 0:
            return True

 

한줄평 : 인덱스값을 활용하고, 언제나 원본 스트링 (또는 리스트)를 수정할 필요가 없다!