Algorithm/Difference Array (1) 썸네일형 리스트형 (Python3) - LeetCode (Medium) : 2381. Shifting Letters II https://leetcode.com/problems/shifting-letters-iidifference array를 사용해본 문제였습니다.📕 풀이방법📔 입력 및 초기화s의 길이 length, 변화량을 저장할 배열 diff, 변화량의 누적값 배열 diff_sums를 선언 후 적절히 초기화합니다.📔 풀이과정단순히 매 shift연산에 대해 for loop를 수행하며 문자를 바꾸게 되면 5만*2로 시간초과를 받게 됩니다. 따라서 O(n)의 연산을 적용하기 위해 변화량을 기록해 누적합을 사용해야 됩니다.1. shifts를 순회하며 현재 shift에 대해 시작 인덱스와 끝 인덱스를 방향에 따라 전처리 해줍니다. 시작인덱스 ~ 끝 인덱스까지 해당 방향이 기록되므로 끝 인덱스 + 1부터는 누적량을 고려해 .. 이전 1 다음