LeetCodd 2337. Move Pieces to Obtain a String(JAVA)

출처 : https://leetcode.com/problems/move-pieces-to-obtain-a-string/description/

#문제

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.

두 문자열 start와 target이 주어집니다. 두 문자열의 길이는 n이며, 각 문자열은 오직 문자 'L', 'R', '_'로만 이루어져 있습니다. 여기서:

문자 'L'과 'R'은 말(pieces)을 나타냅니다. 'L'은 왼쪽으로만 이동할 수 있으며, 바로 왼쪽에 빈칸('_')이 있을 경우에만 이동 가능합니다.'R'은 오른쪽으로만 이동할 수 있으며, 바로 오른쪽에 빈칸('_')이 있을 경우에만 이동 가능합니다.

• 문자 '_'는 빈칸을 나타내며, 'L' 또는 'R'이 차지할 수 있는 공간입니다.

start 문자열의 말들을 임의의 횟수만큼 이동시켜 target 문자열로 만들 수 있는지 판단하여, 가능하면 true를 반환하고, 불가능하면 false를 반환하세요.

접근

문자 L은 왼쪽을 문자R은 오른쪽으로만 이동할수있다. 만약 start에서 target문자열로 변환이 가능하다면

target.charAt(a) == 'L' 이고 start.charAt(b) == 'L' 일때 a<=b 임을 만족해야만한다. R일 경우에는 반대방향이 될것이다.

즉, 문자L은 target에서 start보다 같거나 빠르게 나타나고, 문자R은 start에서 target보다 같거나 빠르게 나타나야만 start에서 target문자열로 변환이 가능하다는걸 볼수있다.

즉, start에서 target으로 변환이 가능하려면 target 문자열에서 등장한 L은 반드시 start 문자열에서 처리되어야하고 start문자열에서 등장한 R은 반드시 target 문자열에서 처리되어야한다.

입력

class Solution{
    public boolean canChange(String start, String target) {

    }
}

L과 R 처리하기

 public boolean canChange(String start, String target) {
    char[] starts = start.toCharArray();
    char[] targets = target.toCharArray();
    //target에서 나온 L을 start에서 처리해야함
    //start에서 나온 R을 target에서 처리해야함
    int l = 0;
    int r = 0;
    for (int i = 0; i < starts.length; i++) {
        if(starts[i] =='L'){
            l--;
        }else if(starts[i] =='R'){
            r++;
        }
        if(targets[i] =='L'){
            l++;
        }else if(targets[i] =='R'){
            r--;
        }
    }
    return l == 0 && r == 0;
}

target에서 L이 나타나면 l을 증가시키고 start에서 L이 나타나면 감소시키고 start에서 R이 나타나면 r을 증가시키고 target에서 R이나타나면 r을 감소시키면서 L과 R을 처리하도록 했다.

L과 R 을 처리할수없는 경우 고려

L과 R을 처리할수없는경우 즉, start에서 target으로 변환할수없는 경우는 어떠것이 있을까?

 

1. target에서 L이 나타났지만 start에서 L을 처리하지 않았고 start에서 R이 나타난경우

즉, start = "_R_L" , target = "L__R" 와 같은 경우에 start에서 target으로 변환하지 못한다.

2. start에서 R이 나타났지만 target에서 R을 처리하지 않았고 target에서 L이 나타난경우

즉, start = "R__L" target = "_L_R" 와 같은 경우에 start에서 target으로 변환하지 못한다.

3. 처리할 문자가 없음에도 문자를 처리한 경우

즉, start = "___RRR" target ="RRR___" or start ="LLL___" target = " ___LLL" 와 같은 경우에 start에서 target으로 변환하지 못한다.

4. L과 R을 모두 처리하지못한 경우, 짝이 맞지않을때

즉, start ="__" target ="R_L" 와 같은 경우에 start에서 target으로 변환하지 못한다.

 

4가지의 경우를 위 코드에 적용시켜보자

 public boolean canChange(String start, String target) {
    char[] starts = start.toCharArray();
    char[] targets = target.toCharArray();
    //target에서 나온 L을 start에서 처리해야함
    //start에서 나온 R을 target에서 처리해야함
    int l = 0;
    int r = 0;
    for (int i = 0; i < starts.length; i++) {
        if(starts[i] =='L'){
            l--;
        }else if(starts[i] =='R'){
            r++;
            //1번 조건
            if(l!=0) return false;
        }
        if(targets[i] =='L'){
            l++;
            //2번 조건
            if(r!=0) return false;
        }else if(targets[i] =='R'){
            r--;
        }

        //3번조건
        if(l<0 || r<0) return false;
    }

    //4번 조건
    return l == 0 && r == 0;
}

최종코드

class Solution {
    public boolean canChange(String start, String target) {
        char[] starts = start.toCharArray();
        char[] targets = target.toCharArray();
        //target에서 나온 L을 start에서 처리해야함
        //start에서 나온 R을 target에서 처리해야함
        int l = 0;
        int r = 0;
        for (int i = 0; i < starts.length; i++) {
            if(starts[i] =='L'){
                l--;
            }else if(starts[i] =='R'){
                r++;
                if(l!=0) return false;
            }
            if(targets[i] =='L'){
                l++; 
                if(r!=0) return false;
            }else if(targets[i] =='R'){
                r--;
            }
            if(l<0 || r<0) return false;
        }
        return l == 0 && r == 0;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        boolean b = s.canChange("R__L", "_LR_");
        System.out.println("b = " + b);
    }
}