넘치게 채우기
[LeetCode] 2381. Shifting Letters II 본문
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;
}
};
'PS > LeetCode' 카테고리의 다른 글
[LeetCode] 1408. String Matching in an Array (0) | 2025.01.07 |
---|---|
[LeetCode] 1769. Minimum Number of Operations to Move All Balls to Each Box (0) | 2025.01.06 |
[LeetCode] 2270. Number of Ways to Split Array (0) | 2025.01.03 |
[LeetCode] 2559. Count Vowel Strings in Ranges (0) | 2025.01.02 |
[LeetCode] 983. Minimum Cost For Tickets (0) | 2024.12.31 |