2381. Shifting Letters II

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

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:11:44

 

---

 

문제 설명

 

 

영소문자로 구성된 문자열 s와, 2차원 정수 배열 shift를 입력이 주어집니다. shift[i] = [start_i, end_i, direction_i]dlek.

모든 i에 대해서, 인덱스 start_i부터 인덱스 end_i(를 포함한)의 모든 문자는 direction_i=1일때 앞으로 shift되며 direction_i = 0일때 뒤로 shift됩니다.

 

문자가 앞으로 shift된다는 의미는, 이 문자를 알파벳 상의 다음 문자로 교체함을 의미합니다('z' 는 'a'가 되도록 순환합니다). 유사하게, 문자가 뒤로 shift된다는 의미는 이 문자를 알파벳 상의 이전 문자로 교체함을 의미합니다('a'는 'z'가 되도록 순환합니다).

 

s에 이러한 shift가 전부 적용된 후의 마지막 문자열을 반환하세요.

---

 

풀이

 

알파벳을 하나의 index로, direction을 이 index에 대한 사칙연산이라고 간주한다면 구간합을 구하는 문제임을 알 수 있다. direction = 1이면 구간의 모든 index에 1을 더하는 셈이고, 그렇지 않다면 구간의 모든 index에 1을 빼는 셈이다.

 

시간복잡도는 O(N + M)이 된다. N은 문자열의 길이, M은 shift의 길이가 되겠다.

 

풀이 코드

class Solution:
    def shiftingCharacter(self, c: str, i: int) -> str:
        return chr((ord(c) - ord('a') + i) % 26 + ord('a'))

    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        sums = [0]*(len(s)+1)
        for start, end, direction in shifts:
            dr = 1 if direction else -1
            sums[start] += dr
            sums[end+1] -= dr

        for i in range(len(s)):
            sums[i+1] += sums[i]
        
        answer = ''.join([self.shiftingCharacter(s[i], sums[i]) for i in range(len(s))])
        return answer