[Swift] 프로그래머스 - 다리를 지나는 트럭

 

추상화된 생각을 코드로 풀어쓰는게 어려웠던 문제다.

그리고 문제에 조건도 주어지지 않았지만 찾아내야 했다.

 

처음에 조건을 잘못 이해하고 sort이용해서 풀다가 생각해낸 풀이로 테스트 케이스는 맞췄다.

 

func solution(_ bridge_length:Int, _ weight:Int, _ truck_weights:[Int]) -> Int {
        var currentSum : Int = 0
        var currentIdx : Int = 0
        var currentQueue = Array(repeating: 0, count: truck_weights.count)
        var answer = 0
    
        while currentQueue[truck_weights.count-1] != -1 {
            answer += 1
            print("++++++지금까지 다리 위 : \(currentQueue), 현재 idx:\(currentIdx), sum: \(currentSum)++++++")
            
            // 기존 큐의 차들 인덱스 넘은 것 있는지 체크
            currentQueue.enumerated().forEach { num in
                print("현재 값: \(num)")
                if num.element <= 0 {
                    print("아직 대기열에 있던 것")
                    return
                }
                
                currentQueue[num.offset] += 1
                if currentQueue[num.offset] > bridge_length {
                    currentQueue[num.offset] = -1
                    print("다리 완전 건너기 처리: \(currentQueue)")
                    currentSum -= truck_weights[num.offset]
                }
            }
            
            // 새로 다리 위에 올리려는 차 검토
            if let item = truck_weights.enumerated().first(where: { $0.offset == currentIdx}) {
                //print("올릴 차는 있음: \(currentSum+item.element), \(currentQueue.filter({ $0 > 0 }).count)")
                var firstZeroOverIdx = currentQueue.firstIndex(where: { $0 > 0}) ?? 0
                var endZeroOverIdx = currentQueue.lastIndex(where: { $0 > 0 }) ?? 0
                if(currentSum+item.element) > weight || firstZeroOverIdx-endZeroOverIdx+1 >= bridge_length {
                    print("-다리 건너려 했으나 못올림")
                    continue
                    //올릴 수 있음
                }else{
                    print("-다리 건널 수 있어서 올림")
                    currentSum += item.element
                    currentQueue[currentIdx] += 1
                    currentIdx += 1
                }
                //올릴 차가 더 이상 없을ㅇ 경우
            }
        }
        return answer
    }

근데 두가지 케이스에서 시간 초과가 발생했다.

Array에 append와 remove를 한다면 시간 복잡도가 높아질거라고 생각해서 위처럼 포인터처럼 움직여줬는데 다른 풀이들을 찾아보니 Swift에는 큐가 없어서 큐처럼 append하고 removeFirst를 해주는 풀이가 많았다...

 

그리고 count세주는 것을 값 하나 할당해서 바꿔줬더니 

케이스 1개에서 시간 초과..

 

그래서 Array의 시간복잡도가 높아지는 것은 언제 고려를 해줘야할까 더 공부가 필요할 것 같다.