https://leetcode.com/problems/shifting-letters-ii
difference array를 사용해본 문제였습니다.
📕 풀이방법
📔 입력 및 초기화
s의 길이 length, 변화량을 저장할 배열 diff, 변화량의 누적값 배열 diff_sums를 선언 후 적절히 초기화합니다.
📔 풀이과정
단순히 매 shift연산에 대해 for loop를 수행하며 문자를 바꾸게 되면 5만*2로 시간초과를 받게 됩니다. 따라서 O(n)의 연산을 적용하기 위해 변화량을 기록해 누적합을 사용해야 됩니다.
1. shifts를 순회하며 현재 shift에 대해 시작 인덱스와 끝 인덱스를 방향에 따라 전처리 해줍니다.
시작인덱스 ~ 끝 인덱스까지 해당 방향이 기록되므로 끝 인덱스 + 1부터는 누적량을 고려해 해당 방향이 그대로 적용되지 않도록 변화를 취소해줘야 합니다. 예시를 들면 다음과 같습니다.
0 ~ 2까지 direction 0이라면 0부터 2까지는 이전 알파뱃으로 변해야하므로 변화량이 -1이고 인덱스 3부터는 해당 변화량이 이후에 적용이 안되도록 +1을 해줘야 합니다.
0 ~ 2까지 direction 1이라면 0부터 2까지 다음 알파뱃으로 변해야하므로 변화량이 +1이고 인덱스 3부터는 해당 변화량이 이후에 적용이 안되도록 -1을 해줘야 합니다.
2. 각 shift연산을 통해 등록되었던 index별 변화량의 누적을 diff_sums에 저장합니다. 이를 통해 i 에서 j까지 얼마만큼 변화해야되는지 값이 O(n)만에 나타납니다.
3. length만큼 for loop를 수행해 각 diff_sum의 변화량만큼 현재 s[i]에서 더해준뒤 26의 나머지 연산으로 순환시켜 문자를 구하고 ans뒤에 붙여줍니다.
📔 정답 출력 | 반환
ans를 반환합니다.
📕 Code
📔 Python3
class Solution:
def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
length = len(s)
diff = [0] * (length+1)
diff_sums = [0]*length
for shift in shifts:
start_index = shift[0]
end_index = shift[1]
direction = shift[2]
if direction == 0:
diff[start_index] -= 1
diff[end_index+1] += 1
else:
diff[start_index] += 1
diff[end_index+1] -= 1
for i in range(0, length):
diff_sums[i] = diff_sums[i-1] + diff[i]
ans = ''
for i in range(length):
changed = chr((ord(s[i]) - ord('a') + diff_sums[i])%26 + ord('a'))
ans += changed
return ans*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.