2381. Shifting Letters II

https://leetcode.com/problems/shifting-letters-ii/description/?envType=daily-question&envId=2025-01-05

 

 

 

 

 

shift = [0, 0, 0]이 주어질 때, shift[0]과 shift[1]은 시작 인덱스와 끝 인덱스고, shift[2]는 움직이는 방향을 정해준다.

1인 경우엔, 'a' -> 'b'와 같이 옮겨주고

0인 경우엔 'b' -> 'a'와 같이 뒤로 한칸 이동한다.

 

이 문제 역시도 constraints 조건으로 인해서 시간복잡도를 O(N^2) 미만으로 줄여야했다. 그래서 이전 문제와 비슷하게 누적합, 차분 배열을 사용한 방식으로 해결했다.

 

이전 문제와 살짝 다른 부분은 1인 경우엔 시작점++, 끝점-- 라면,

0인 경우엔 시작점--, 끝점++으로 해주었다.

 

정답 코드

class Solution {
    public String shiftingLetters(String s, int[][] shifts) {
        
        int n = s.length();
        int [] freq = new int[n+1];

        for(int [] shift : shifts) {
            int st = shift[0];
            int en = shift[1];
            int dir = shift[2];

            if (dir == 1) {
                freq[st]++;
                freq[en+1]--;
            }

            else {
                freq[st]--;
                freq[en+1]++;
            }
        }

        System.out.println("freq: " + freq[0]);
        for(int i = 1; i < n; i++) {
            freq[i] += freq[i-1];
            System.out.println("freq: " + freq[i]);
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            char c = s.charAt(i);

            int shift = (freq[i] % 26 + 26) % 26;
            char newChar = (char)((c - 'a' + shift) % 26 + 'a');
           
            sb.append(newChar);
        }

        return sb.toString();
    }
}

 

 

문제를 다 풀어놓고 더했을 때 'z'의 범위를 넘어갈 때, 뺐을 때 'a'보다 작을때와 같은 케이스가 까다롭게 느껴졌다.

int shift = (freq[i] % 26 + 26) % 26;
char newChar = (char)((c - 'a' + shift) % 26 + 'a');

 

shift에 + 26을 해준 이유는 음수까지 고려했기 때문이다. 이렇게 했을 때, freq[i]가 -1이라면 25로 변환이 되어 원하는 결과를 얻을 수 있다.