[프로그래머스 lv.3] 합승 택시 요금 (파이썬)

LEE·2022년 3월 2일
0

프로그래머스

목록 보기
2/25
post-thumbnail

문제

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

  • 각 지점은 1 ~ n으로 표시
  • s에서 출발해서 도착지는 각각 a와 b
  • 지점 사이의 예상 택시 요금을 나타내는 fares
  • 만약 합승하지 않고 각자 이동하는 경우가 더 저렴하면 합승하지 않아도 된다

  • 양방향
  • 3 <= n <= 200 인 자연수
  • 1 <= s, a, b <= n 인 자연수이고 모두 다른 값이다

풀이

  1. 최소요금 문제니까 heapq를 사용하자
  2. i에서 j로가는 최소요금을 구하는 함수를 만들자
  3. 합승이 없는 경우, a까지 합승하고 b로 가는경우, b까지 합승하고 a로 가는 경우 중 제일 작은 값을 구하자 (=> answer에 담아두기)
  4. 합승의 목적지가 a와 b가 아니면서 answer보다 작은 경우 탐색

코드

from heapq import heappush, heappop
def solution(n, s, a, b, fares):
    INF = 0
    adj = [[] for _ in range(n+1)]
    for c, d, f in fares:
        adj[c].append([d, f])
        adj[d].append([c, f])
        INF += f

    def fee(i, j):                          # i에서 j로 가는 최소 요금 계산
        Q = []
        visited = [INF] * (n+1)
        heappush(Q, [0, i])
        visited[i] = 0
        while Q:
            p, v = heappop(Q)
            if p > INF: continue
            if visited[v] < p: continue
            for w, wp in adj[v]:
                np = p + wp
                if visited[w] > np:
                    visited[w] = np
                    heappush(Q, [np, w])
        return visited[j]
    sa = fee(s, a)
    sb = fee(s, b)
    ab = fee(a, b)
    ba = fee(b, a)
    answer = min(sa+sb, sa+ab, sb+ba)
    INF = answer
    for i in range(n+1):                    # s->i + i->a + i->b
        if i in [s, a, b]: continue
        tmp = fee(s, i)
        if tmp >= answer: continue
        tmp += fee(i, a)
        if tmp >= answer: continue
        tmp += fee(i, b)
        if tmp < answer:
            answer = tmp
            INF = answer

    return answer

후기

이 문제는 정확성과 효율성을 모두 살피는 문제였다
처음 문제를 읽고 플로이드-와샬 문제라고 생각했지만 아직 해당 알고리즘을 공부하지 못했기 때문에 heapq를 이용하여 문제를 해결하고자 했다
오랜만에 heapq를 활용한 문제를 풀어서 코드가 덕지덕지인 느낌이다 그래서 효율적이지 못한 느낌.
다음에 조금 더 효율적인 방법이 없는지 알아봐야겠다

정확성 테스트

테스트 1 〉	통과 (0.06ms, 10.2MB)
테스트 2 〉	통과 (0.07ms, 10.5MB)
테스트 3 〉	통과 (0.04ms, 10.3MB)
테스트 4 〉	통과 (0.31ms, 10.4MB)
테스트 5 〉	통과 (0.24ms, 10.3MB)
테스트 6 〉	통과 (0.42ms, 10.3MB)
테스트 7 〉	통과 (0.43ms, 10.1MB)
테스트 8 〉	통과 (0.49ms, 10.2MB)
테스트 9 〉	통과 (0.65ms, 10.3MB)
테스트 10 〉	통과 (0.79ms, 10.4MB)

효율성 테스트

테스트 1 〉	통과 (28.83ms, 10.3MB)
테스트 2 〉	통과 (212.08ms, 10.7MB)
테스트 3 〉	통과 (71.25ms, 10.4MB)
테스트 4 〉	통과 (55.51ms, 10.3MB)
테스트 5 〉	통과 (82.95ms, 10.4MB)
테스트 6 〉	통과 (80.05ms, 10.3MB)
테스트 7 〉	통과 (2399.91ms, 16MB)
테스트 8 〉	통과 (2331.34ms, 16.1MB)
테스트 9 〉	통과 (1966.60ms, 16.1MB)
테스트 10 〉	통과 (1898.15ms, 16MB)
테스트 11 〉	통과 (1824.10ms, 16.1MB)
테스트 12 〉	통과 (1207.62ms, 13.1MB)
테스트 13 〉	통과 (1043.78ms, 13.2MB)
테스트 14 〉	통과 (998.45ms, 13.2MB)
테스트 15 〉	통과 (1078.97ms, 13.2MB)
테스트 16 〉	통과 (80.20ms, 10.2MB)
테스트 17 〉	통과 (78.03ms, 10.2MB)
테스트 18 〉	통과 (89.42ms, 10.3MB)
테스트 19 〉	통과 (163.27ms, 10.5MB)
테스트 20 〉	통과 (231.44ms, 10.7MB)
테스트 21 〉	통과 (219.54ms, 10.6MB)
테스트 22 〉	통과 (1333.76ms, 13.2MB)
테스트 23 〉	통과 (1176.34ms, 13.2MB)
테스트 24 〉	통과 (1064.85ms, 13.1MB)
테스트 25 〉	통과 (45.62ms, 10.2MB)
테스트 26 〉	통과 (52.09ms, 10.2MB)
테스트 27 〉	통과 (243.19ms, 10.7MB)
테스트 28 〉	통과 (250.71ms, 10.5MB)
테스트 29 〉	통과 (25.48ms, 10.3MB)
테스트 30 〉	통과 (26.85ms, 10.2MB)
profile
쑥쑥 개발자

0개의 댓글