넘치게 채우기

[LeetCode] 2381. Shifting Letters II 본문

PS/LeetCode

[LeetCode] 2381. Shifting Letters II

riveroverflow 2025. 1. 5. 20:10
728x90
반응형

https://leetcode.com/problems/shifting-letters-ii/description/

leetcode - Shifting Letters II

문제 유형: 문자열 처리, 슬라이딩 윈도우, 라인 스위핑, 구간합

문제 난이도: Medium

 

문제

You are given a string s of lowercase English letters and a 2D integer array shifts where shifts[i] = [starti, endi, directioni]. For every i, shift the characters in s from the index starti to the index endi (inclusive) forward if directioni = 1, or shift the characters backward if directioni = 0.

Shifting a character forward means replacing it with the next letter in the alphabet (wrapping around so that 'z' becomes 'a'). Similarly, shifting a character backward means replacing it with the previous letter in the alphabet (wrapping around so that 'a' becomes 'z').

Return the final string after all such shifts to s are applied.

 

영소문자로 된 문자열 s를 받는다.

shifts라는 2D배열도 받는데, [starti, endi, directioni]는 [starti, endi]의 범위에 direction가 1인경우 전방향 쉬프트, 0인경우 역방향 쉬프트하라는 의미이다.

('a'에서 역방향 쉬프트하면 'z'가 된다. 전방향 쉬프트하면 'b'가 될 것이다.)

적용 후의 문자열을 리턴하시오.

 

풀이

매번 반영하는 것은 비효율적이다.

모든 shifts의 연산들을 하나로 묶어야 한다.

쉬프트 변화량을 저장하는 dshifts배열을 만들어서, dshifts[i] = i인덱스부터의 쉬프트 변화량을 저장한다.

shifts[i] = [start, end, dir]가 저장되어있으므로,

dshifts[start]에 dir이 1인경우 1을, 아니면 -1을 저장하고, dshifts[end+1]에 dir이 1인경우 -1을, 아니면 1을 저장한다.

 

문자열을 순회하면서, 해당 인덱스에 적절한 쉬프트 횟수들별로 적용해서 문자를 변환한다.

문자열을 리턴한다.

 

코드

C++

class Solution {
public:
    void shiftChar(string &s, int i, int dshift) {
        dshift = (dshift % 26 + 26) % 26;
        s[i] = 'a' + (s[i] - 'a' + dshift) % 26;
    }

    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        int n = s.size();
        vector<int> dshifts(n + 1, 0);

        for (const auto &shift : shifts) {
            int start = shift[0], end = shift[1], direction = shift[2];
            dshifts[start] += (direction == 1 ? 1 : -1);
            dshifts[end + 1] += (direction == 1 ? -1 : 1);
        }

        int dshift = 0;
        for (int i = 0; i < n; ++i) {
            dshift += dshifts[i];
            shiftChar(s, i, dshift);
        }

        return s;
    }
};
728x90
반응형