-
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
접근 방법
- 모든 node 사이의 최소 요금 정보가 필요.
- >>> 플로이드 알고리즘
- start -> n번 node -> 각자 목적지로의 요금 계산 >> n개의 sum을 갖는 array를 만들 수 있음, 혹은 max비교
- 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틀린 접근 방법
- 문제를 보고 플로이드 알고리즘을 써야 함을 인지.
- 하지만 다익스트라 알고리즘밖에 모른다;
- 그렇다면 모든 노드에 대해 다익스트라 알고리즘을 사용하여, 각 노드의 최단거리를 모두 구한다
- 얻은 다익스트라 맵을 통하여 최소 합승요금을 구한다.
- 그리고 효율성에서 틀렸다.
틀린 코드
더보기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'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
dijkstra(최단거리)_LeetCode_1514 [swift] (0) 2022.05.25 Dijkstra(최단거리)_programmers_가장 먼 노드 (0) 2022.05.25 문자열_프로그래머스_시저 암호 [swift] (0) 2022.05.18 Dijkstra(최단거리)_programmers_SW2018 배달 [swift] (0) 2022.05.17 Stack_프로그래머스_괄호 회전하기 [swift] (0) 2022.05.11