Leetcode[day14] - Perform String Shifts

You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [direction, amount]:
- direction can be 0 (for left shift) or 1 (for right shift).
- amount is the amount by which string s is to be shifted.
- A left shift by 1 means remove the first character of s and append it to the end.
- Similarly, a right shift by 1 means remove the last character of s and add it to the beginning.
Return the final string after all operations.

 

 

Input: s = "abcdefg", shift = [[1,1],[1,1],[0,2],[1,3]]
Output: "efgabcd"
Explanation: 
[1,1] means shift to right by 1. "abcdefg" -> "gabcdef"
[1,1] means shift to right by 1. "gabcdef" -> "fgabcde"
[0,2] means shift to left by 2. "fgabcde" -> "abcdefg"
[1,3] means shift to right by 3. "abcdefg" -> "efgabcd"

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - input s와 shift 배열이 주어질 때, shift의 배열만큼 string을 이동시키라는 알고리즘이었다.

 - 먼저, shift 배열을 줄여주는 것을 선택했다. 0은 왼쪽, 1은 오른쪽이기 때문에, 0일 때는 -n, 1일 때는 +n을 해줬다.

 - 그래서 배열의 길이만큼 0과 1을 이용해서 최종적으로 이동하는 directionAmout가 구해진다.

 - driectionAmount를 input s의 길이만큼 나머지를 구해준다. 이는 directionAmount가 클 경우, 불필요하게 shift를 하는 것을 막아줄 것이다.

 - 그리고, 이동할 길이를 최적한 변수를 optimizedDirectionAmount라고 했을 때, s를 이동시켜준다.

 - 이 때는 substring()을 활용해서 잘 이동시켜주자.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 쉬운 문제였다.

 

3. 내가 작성한 알고리즘

 

class Solution {
    public String stringShift(String s, int[][] shift) {
        String result = "";
        int directionAmount = optimizeShiftCommand(shift);
        int optimizedDirectionAmount = optimizeDirectionAmount(s, directionAmount);
        //directionAmount < 0 is shift left, else shift right
        System.out.println(directionAmount);
        System.out.println(optimizedDirectionAmount);
        
        int inputLength = s.length();
        if(directionAmount < 0){
            result = s.substring(optimizedDirectionAmount, inputLength) +
                s.substring(0, optimizedDirectionAmount);
        }
        else{
            result = s.substring(inputLength - optimizedDirectionAmount, inputLength) +
                s.substring(0, inputLength - optimizedDirectionAmount);
        }
        return result;   
    }
    
    //[[0,1],[1,2]]
    public int optimizeShiftCommand(int[][] shift){
        int directionAmount = 0;
        for(int i=0; i < shift.length; i++){
            int[] shiftCommand = shift[i]; 
            int shiftDirection = shiftCommand[0];
            int shiftDirectionAmountPart = shiftCommand[1];
            //0 is left, 1 is right
            if(shiftDirection == 0){
                directionAmount -= shiftDirectionAmountPart;
            }else{
                directionAmount += shiftDirectionAmountPart;
            }
        }
        return directionAmount;
    }
    
    public int optimizeDirectionAmount(String s, int directionAmount){
        int wordSize = s.length();
        int directionAmountAbs = Math.abs(directionAmount);
        return directionAmountAbs % wordSize;
    }
}

 

4. 내가 작성한 알고리즘 결과

 

 

5. 내가 작성한 알고리즘 생각해보기

 

optimizeShiftCommand() 메소드를 실행할 때, shift 해야하는 길이를 구하기 위해서 O(N)이 사용되었다.

그 외에는 별도의 로직이 없기 때문에, 충분히 빠를 것이다. 공간복잡도도 별도로 사용한 것이 없으니 빠르겠지.

 

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3299/

Account Login - LeetCode