[Swift] [67일차] 1409_LEET 공 옮기기

1769. Minimum Number of Operations to Move All Balls to Each Box

문제 설명

1. 0과1로 이루어진 n길이의 string이 주어진다.
2. 이걸 각자 그 박스에 인접한칸으로 1칸씩 한개씩만 옮길 수 있다.
3. 그러면 answer[i]번째에 공을 다 모으기 위한 카운팅을 각자 인덱스별로 담아서 return

---

문제풀이

1. 일단은 칸 이동에 드는 카운팅이 어떤 식으로 나오는지 알아봤을때,
2. 공이있는칸 - 찾고자하는 i 를 절댓값 씌워주면 해당칸에서 i까지 몇번움직여야하는지 나오니까
3. 이걸 전체를 돌면서abs(index-i) 해주면 될 것 같다.

class Solution {
    func minOperations(_ boxes: String) -> [Int] {
        var boxes = Array(boxes).map { Int(String($0))! }

        var answer = [Int]()
        var index = 0

        // 넣고자하는 i번째와의 거리를 더해주면됨
        while index < boxes.count {
            var counting = 0
            for i in 0 ..< boxes.count {
                if boxes[i] == 1 {
                    counting += abs(index - i)
                }
            }
            answer.append(counting)
            index += 1
        }

        return answer
    }
}

보니까 엄청나게 분포가 다양하더라, 4ms는 얼마나 빠른건지 한번 둘러봤다.

---

타인의 코드

class Solution {
    func minOperations(_ boxes: String) -> [Int] {
        let boxesArray = Array(boxes)
        var result = Array(repeating: 0, count: boxes.count)
        
        var count = 0
        
        for i in 1..<boxes.count {
            if boxesArray[i - 1] == "1" {
                count += 1
            }
            
            result[i] = result[i - 1] + count
        }
        
        count = 0
        var accumulation = 0

        for i in stride(from: boxes.count - 2, through: 0, by: -1) {
            if boxesArray[i + 1] == "1" {
                count += 1
            }
            
            accumulation += count
            result[i] += accumulation
        }
        
        return result
    }
}

보니까 엄청나게 분포가 다양하더라. 4ms는 얼마나 빠른건지 한번 둘러봤다.
타인의 코드를 보니, 나처럼 String을 Array로 변환하고 다시 Int로 바꿔줄 필요 없이 바로 처리하는 방식을 사용했더라. 그래서 그 부분에서 차이가 발생한 것 같아서 내 코드도 수정해봤다. 그런데도 오히려 느려지거나 별 차이가 없었는데, 알고 보니 abs(index - i) 부분에서 시간 차이가 발생한 것 같다. 이 부분은 이중 반복문을 사용하면서 모든 인덱스 페어에 대해서 거리 계산할 때 시간 복잡도가 O(n^2)로 증가해서 그런 것 같다.