ABOUT ME

Today
Yesterday
Total
  • Dijkstra(최단거리)_programmers_2021kakao 합승택시요금[swift]
    알고리즘/알고리즘 문제풀이 2022. 5. 18. 19:52

    https://programmers.co.kr/learn/courses/30/lessons/72413

     

    코딩테스트 연습 - 합승 택시 요금

    6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4

    programmers.co.kr

     

    접근 방법

    1. 모든 node 사이의 최소 요금 정보가 필요.
    2. >>> 플로이드 알고리즘
    3. start -> n번 node -> 각자 목적지로의 요금 계산 >> n개의 sum을 갖는 array를 만들 수 있음, 혹은 max비교
    4. return array.min()

    정답 코드

    더보기
    import Foundation
    
        
        var map = [[Int]]()
    
        func solution(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {
            // 초기 셋팅
            createMap(size: n)
            inject(fares: fares)
            
            플로이드(size: n - 1)
            var fareSum = [Int]()
            
            for node in 0..<n {
                
                if map[s-1][node] < 0 ||
                    map[node][a-1] < 0 ||
                    map[node][b-1] < 0 {
                    continue
                }
                
                let sum = map[s-1][node] + map[node][a-1] + map[node][b-1]
                
                fareSum.append(sum)
            }
            
            return fareSum.min() ?? 0
        }
    
        func 플로이드(size: Int) {
            for k in 0...size {
                for start in 0...size {
                    for end in 0...size {
                        
                        if map[k][end] == -1 ||
                            map[start][k] == -1 {
                            continue
                        }
                        
                        if map[start][end] > map[start][k] + map[k][end] ||
                            map[start][end] < 0 {
                            map[start][end] = map[start][k] + map[k][end]
                        }
                    }
                }
            }
        }
    func inject(fares: [[Int]]) {
            
            for fare in fares {
                map[fare[0]-1][fare[1]-1] = fare[2]
                map[fare[1]-1][fare[0]-1] = fare[2]
            }
        }
    
        func createMap(size: Int) {
            var tempMap = [[Int]].init(repeating: [Int].init(repeating: -1, count: size), count: size)
            
            for i in 0..<size {
                tempMap[i][i] = 0
            }
            
            map = tempMap
        }

    성적

    더보기
    정확성 테스트
    테스트 1 통과 (0.10ms, 16.2MB)
    테스트 2 통과 (0.09ms, 16.2MB)
    테스트 3 통과 (0.09ms, 16.3MB)
    테스트 4 통과 (0.29ms, 16.2MB)
    테스트 5 통과 (0.33ms, 16.4MB)
    테스트 6 통과 (0.56ms, 16.6MB)
    테스트 7 통과 (0.42ms, 16.3MB)
    테스트 8 통과 (0.71ms, 16.4MB)
    테스트 9 통과 (0.90ms, 16.6MB)
    테스트 10 통과 (1.16ms, 16.3MB)
    효율성 테스트
    테스트 1 통과 (188.74ms, 16.5MB)
    테스트 2 통과 (756.43ms, 17.1MB)
    테스트 3 통과 (874.78ms, 16.7MB)
    테스트 4 통과 (849.63ms, 16.8MB)
    테스트 5 통과 (907.05ms, 16.8MB)
    테스트 6 통과 (846.92ms, 17MB)
    테스트 7 통과 (1799.08ms, 22.9MB)
    테스트 8 통과 (1628.99ms, 22.9MB)
    테스트 9 통과 (1771.10ms, 22.9MB)
    테스트 10 통과 (1740.40ms, 23MB)
    테스트 11 통과 (1815.20ms, 23MB)
    테스트 12 통과 (1786.79ms, 19.7MB)
    테스트 13 통과 (1760.90ms, 19.7MB)
    테스트 14 통과 (1596.63ms, 19.8MB)
    테스트 15 통과 (1835.04ms, 19.7MB)
    테스트 16 통과 (759.78ms, 16.7MB)
    테스트 17 통과 (706.89ms, 16.8MB)
    테스트 18 통과 (771.80ms, 16.7MB)
    테스트 19 통과 (1496.05ms, 17.1MB)
    테스트 20 통과 (1647.29ms, 17.2MB)
    테스트 21 통과 (1627.14ms, 17.2MB)
    테스트 22 통과 (1826.29ms, 19.5MB)
    테스트 23 통과 (1607.63ms, 19.7MB)
    테스트 24 통과 (1752.68ms, 19.6MB)
    테스트 25 통과 (529.54ms, 16.9MB)
    테스트 26 통과 (513.38ms, 16.6MB)
    테스트 27 통과 (1650.07ms, 17.2MB)
    테스트 28 통과 (1603.45ms, 17.2MB)
    테스트 29 통과 (148.54ms, 16.6MB)
    테스트 30 통과 (141.50ms, 16.6MB)
    채점 결과
    정확성: 50.0
    효율성: 50.0
    합계: 100.0 / 100.0

     

    틀린 접근 방법

    1. 문제를 보고 플로이드 알고리즘을 써야 함을 인지.
    2. 하지만 다익스트라 알고리즘밖에 모른다;
    3. 그렇다면 모든 노드에 대해 다익스트라 알고리즘을 사용하여, 각 노드의 최단거리를 모두 구한다
    4. 얻은 다익스트라 맵을 통하여 최소 합승요금을 구한다.
    5. 그리고 효율성에서 틀렸다.

    틀린 코드

    더보기
    class programmers_2021kakao_합승택시요금 {
        
        var map = [[Int]]()
        var minimumFare = [Int]()
        var queue = [(Int,Int)]() { // (node,fare)
            didSet{
                queue.sort( by: {
                    $0.1 < $1.1
                })
            }
        }
    
        func solution(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {
            // 초기 셋팅
            createMap(size: n)
            inject(fares: fares)
            
            var minimumFareArray = [[Int]]()
            
            for start in 1...n {
                
                // 최단거리 초기화
                minimumFare = [Int].init(repeating: -1, count: n)
                minimumFare[start-1] = 0
                //queue에 초기값 추가
                queue.append( (start-1,0) )
                
                while !queue.isEmpty {
                    let target = queue.removeFirst()
    
                    if minimumFare[target.0] != -1 &&
                       minimumFare[target.0] < target.1 {
                           continue
                       }
                    
                    dijkstra(start: target.0)
                    
                }
                minimumFareArray.append(minimumFare)
            }
            
            let minimumFareFromStart = minimumFareArray[s-1]
            
            var fareSum = [Int]()
            
            for node in 0..<n {
                
                if minimumFareFromStart[node] < 0 ||
                    minimumFareArray[node][a-1] < 0 ||
                    minimumFareArray[node][b-1] < 0 {
                    continue
                }
                
                let sum = minimumFareFromStart[node] + minimumFareArray[node][a-1] + minimumFareArray[node][b-1]
                
                fareSum.append(sum)
            }
            
            return fareSum.min() ?? 0
        }
    
        func dijkstra(start: Int) {
            for (node,fare) in map[start].enumerated() {
                
                if fare < 0 {
                    continue
                }
                
                let comparative = minimumFare[start] + fare
                
                if minimumFare[node] > comparative ||
                    minimumFare[node] < 0 {
                    minimumFare[node] = comparative
                    queue.append((node, comparative))
                }
            }
        }
    
        func inject(fares: [[Int]]) {
            
            for fare in fares {
                map[fare[0]-1][fare[1]-1] = fare[2]
                map[fare[1]-1][fare[0]-1] = fare[2]
            }
        }
    
        func createMap(size: Int) {
            var tempMap = [[Int]].init(repeating: [Int].init(repeating: -1, count: size), count: size)
            
            for i in 0..<size {
                tempMap[i][i] = 0
            }
            
            map = tempMap
        }
        
    }

    성적

    반성 : 다익스트라 맵을 얻는 것은 비효율적이다. 

    더보기
    정확성 테스트
    테스트 1 통과 (0.45ms, 16.6MB)
    테스트 2 통과 (0.55ms, 16.3MB)
    테스트 3 통과 (0.35ms, 16.6MB)
    테스트 4 통과 (1.91ms, 16.5MB)
    테스트 5 통과 (1.17ms, 16.3MB)
    테스트 6 통과 (2.24ms, 16.7MB)
    테스트 7 통과 (1.89ms, 16.7MB)
    테스트 8 통과 (3.27ms, 16.3MB)
    테스트 9 통과 (4.08ms, 16.7MB)
    테스트 10 통과 (6.02ms, 16.7MB)
    효율성 테스트
    테스트 1 실패 (시간 초과)
    테스트 2 실패 (시간 초과)
    테스트 3 실패 (시간 초과)
    테스트 4 실패 (시간 초과)
    테스트 5 통과 (2237.36ms, 17.1MB)
    테스트 6 통과 (2322.28ms, 17.2MB)
    테스트 7 실패 (시간 초과)
    테스트 8 실패 (시간 초과)
    테스트 9 통과 (3086.98ms, 22.9MB)
    테스트 10 통과 (3262.14ms, 22.8MB)
    테스트 11 통과 (3096.40ms, 23.1MB)
    테스트 12 실패 (시간 초과)
    테스트 13 실패 (시간 초과)
    테스트 14 실패 (시간 초과)
    테스트 15 실패 (시간 초과)
    테스트 16 통과 (2022.31ms, 17.4MB)
    테스트 17 통과 (1947.27ms, 17.2MB)
    테스트 18 통과 (1792.58ms, 17MB)
    테스트 19 실패 (시간 초과)
    테스트 20 실패 (시간 초과)
    테스트 21 실패 (시간 초과)
    테스트 22 실패 (시간 초과)
    테스트 23 실패 (시간 초과)
    테스트 24 실패 (시간 초과)
    테스트 25 통과 (1270.40ms, 17.4MB)
    테스트 26 통과 (1128.14ms, 17.2MB)
    테스트 27 실패 (시간 초과)
    테스트 28 실패 (시간 초과)
    테스트 29 실패 (시간 초과)
    테스트 30 실패 (시간 초과)
    채점 결과
    정확성: 50.0
    효율성: 16.7
    합계: 66.7 / 100.0

     

     

Designed by Tistory.