PrefixSum_Leetcode_2381. Shifting Letters II [swift]

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

 

문제접근

1. shift의 정보를 Dictionary의 형태로 변형한다.
   1. String의 특정 index에 대한 이동 값을 모두 더한 뒤, 수행하기 위해서
2. 매개변수로 전달된 초기 String s를 Dictionary의 정보를 바탕으로 다른 알파벳으로 변환한다.

 

오답풀이

실패 사유: 시간초과. O(mn)

gpt가 제안하는 해결방법: 차분배열을 쓰면 O(m+n)이 가능하다.

class Solution {
    func shiftingLetters(_ s: String, _ shifts: [[Int]]) -> String {
        var instructionMap = [Int: Int]()
        for infos in shifts {
            for index in infos[0]...infos[1] {
                if infos[2] == 1 {
                    instructionMap[index, default: 0] += 1
                } else {
                    instructionMap[index, default: 0] -= 1
                }
            }
        }

        let sol: [Character] = s.enumerated().map { (index, char) in
            if let inst = instructionMap[index] {
                return moveCharacter(target: char, magnitude: inst)
            } else {
                return char
            }
        }
        
        return String(sol)
    }

    func moveCharacter(target: Character, magnitude: Int) -> Character {
        let list = Array("abcdefghijklmnopqrstuvwxyz")
        let size = list.count
        guard let targetIndex = list.firstIndex(of: target) else { return target }
        let adjustMagnitude = ((magnitude % size) + size) % size
        let returnIndex = (targetIndex + adjustMagnitude) % size

        return list[returnIndex]
    }
}

정답풀이

class Solution {
    func shiftingLetters(_ s: String, _ shifts: [[Int]]) -> String {
        let n = s.count
        var diff = [Int](repeating: 0, count: n)

        for infos in shifts {
            let value = infos[2] == 1 ? 1 : -1

            diff[infos[0]] += value

            if infos[1] + 1 < n {
                diff[infos[1] + 1] -= value
            }
        }

        var sol = Array(s)
        var currentShifting = 0

        for (index, differ) in diff.enumerated() {
            currentShifting += differ
            guard currentShifting != 0 else { continue }
            sol[index] = moveCharacter(target: sol[index], magnitude: currentShifting)
        }
        
        return String(sol)
    }

    func moveCharacter(target: Character, magnitude: Int) -> Character {
        let list = Array("abcdefghijklmnopqrstuvwxyz")
        let size = list.count
        guard let targetIndex = list.firstIndex(of: target) else { return target }
        let adjustMagnitude = ((magnitude % size) + size) % size
        let returnIndex = (targetIndex + adjustMagnitude) % size

        return list[returnIndex]
    }
}