글 읽기 - [Swift] 어느부분이 잘못된건지 모르겠습니다.

whdvy3 2년 전 1

신기하게도 NodePriority 구조체안의 함수를 위에두고 변수를 밑에두면 시간초과가 나고,

저 상태에서 NodePriority 구조체안의 함수안의 '<'를 '>'로 바꿔도 시간초과가 나고,

지금상태에서는 틀렸다고나옵니다.

import Foundation
public struct Heap<T> {
    var nodes: [T] = []
    let comparer: (T, T) -> Bool
    
    var isEmpty: Bool {
        return nodes.isEmpty
    }
    init(comparer: @escaping (T,T) -> Bool) {
        self.comparer = comparer
    }
    func peek() -> T? {
        return nodes.first
    }
    mutating func insert(_ element: T) {
        var index = nodes.count
        nodes.append(element)
        
        while index > 0, !comparer(nodes[index], nodes[(index - 1) / 2]) {
            nodes.swapAt(index, (index - 1) / 2)
            index = (index - 1) / 2
        }
    }
    mutating func delete() -> T? {
        guard !nodes.isEmpty else {
            return nil
        }
        if nodes.count == 1 {
            return nodes.removeFirst()
        }
        let result = nodes.first
        nodes.swapAt(0, nodes.count - 1)
        _ = nodes.popLast()
        
        var index = 0
        while index < nodes.count {
            let left = index * 2 + 1
            let right = left + 1
            
            if right < nodes.count {
                if comparer(nodes[left], nodes[right]),
                   !comparer(nodes[right], nodes[index]) {
                    nodes.swapAt(right, index)
                    index = right
                } else if !comparer(nodes[left], nodes[index]) {
                    nodes.swapAt(left, index)
                    index = left
                } else {
                    break
                }
            } else if left < nodes.count {
                if !comparer(nodes[left], nodes[index]) {
                    nodes.swapAt(left, index)
                    index = left
                } else {
                    break
                }
            } else {
                break
            }
        }
        
        return result
    }
}
extension Heap where T: Comparable {
    init() {
        self.init(comparer: >)
    }
}

struct NodePriority: Comparable{
    var priorty: Int
    var node: String
    
    
    static func < (lhs: NodePriority, rhs: NodePriority) -> Bool{
        lhs.priorty < rhs.priorty
    }
}

let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
let v = arr[0]
let e = arr[1]
let start = String(readLine()!)
var graph = [String : [String:Int]]()
let INF = Int.max

for i in 1...v{
    graph[String(i)] = [:]
}

for _ in 1...e {
    let indirectLine = readLine()!.split(separator: " ").map{String($0)}
    graph[indirectLine[0]]?.updateValue(Int(indirectLine[2])!, forKey: indirectLine[1])
}

func dijkstra(_ graph: [String: [String: Int]],_ start: String){
    var distances = [String: Int]()
    var priorityQueue = Heap<NodePriority>()
    priorityQueue.insert(NodePriority(priorty: 0, node: start))
    for key in graph.keys {
        let value = key == start ? 0 : INF
        distances.updateValue(value, forKey: key)
    }


    while !priorityQueue.isEmpty {
        guard let pop = priorityQueue.delete() else {break}

        if distances[pop.node]! < pop.priorty {
                  continue
              }

        for (node, indirectLine) in graph[pop.node]! {
            let distance = indirectLine + pop.priorty
            if distance < distances[node]! {
                distances[node] = distance
                priorityQueue.insert(NodePriority.init(priorty: distance, node: node))
            }
        }

    }
    
    for i in 1...v{
        if distances[String(i)] == INF {
            print("INF")
        }else {
            print(distances[String(i)]!)
        }
    }
}

dijkstra(graph, start)

nhg1113 2년 전 2

방금 저도 삽질해가며 푼 결과 시간을 줄이는 여러 방법을 찾았습니다.

첫번째는 다익스트라 함수 내부에 있는 let distance 변수를 생성하지 않는 것이었습니다.

저도 처음에는

let distance와

let next

라는 변수를 두 개 만들어서 둘을 따로 사용했는데, 이 부분만 제거하고 값을 바로 할당해주니 시간초과를 벗어날 수 있었습니다.

일단은 이거 하나만 했는데도 시간초과에서 탈출했습니다.

변수 생성없이도 값을 할당 할 수 있는 부분은 그렇게 하는 편이 좋은 것 같습니다.

두번째는 라이노 님의 fileIO 클래스를 사용하는 것입니다.

제가 처음 성공했을 때는 700ms 정도 나왔는데, 라이노 님의 fileIO 클래스를 적용하고 나니 110ms 대로 현재 속도에선 1등입니다.

둘 중 하나만 해도 시간 초과를 면할 거 같습니다.

다만 첫번째 방법은 시간을 얼마나 줄여주는 지는 잘 모르겠어서 일단 한 번 적용해보는걸 추천합니다.

출력할 때 print함수를 여러번 사용하게끔 두면 시간이 더 오래걸립니다.

var answer = ""

를 만들어서 answer에 계속 답과 개행문자를 append하는 식으로 큰 문자열을 하나 만든다음에 print함수를 한 번만 사용해서 출력하는 방식이 시간 감소에 더 도움이 됩니다.

whdvy3 2년 전 1

여기서도 도움을 주시네요 ㅠㅠ

정말 감사드립니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[Swift] 어느부분이 잘못된건지 모르겠습니다.

whdvy3 2년 전 1

nhg1113 2년 전 2

whdvy3 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말