[프로그래머스] 탐욕법(Greedy) - 2

섬 연결하기

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

내 풀이 - 실패

answer = float('inf')

def solution(n, costs):
    ### 그래프처럼 섬 연결 => dic 에 저장 ###
    dic = {i:[] for i in range(n)}
    for a, b, c in costs:
        dic[a].append((b, c))
        dic[b].append((a, c))
        
    ### 재귀로 최소 cost 찾기 ###
    def func(start, end, cost, path, n):
        global answer
        if start == end:
            ### 모든 지점을 다 지났을 때의 최솟값을 answer 에 저장 ###
            if len(path) == n:
                answer = min(answer, cost)
            return cost
        
        ans = float('inf')
        for i, c in dic[start]:
            if i not in path:
                ans = min(ans, func(i, end, cost+c, path+[i], n))
        return ans
    
    ### 섬 개수만큼 dp 생성 ###
    dp = []
    for i in range(n):
        dp.append([float('inf')]*n)
        
    for i in range(n):
        for j in range(i+1, n):
            dp[i][j] = func(i, j, 0, [i], n)
    
    return answer

1. 그래프처럼 섬들을 연결해서 dic 에 저장

2. 재귀 함수로 각 섬들 사이의 최소 cost 를 구해서 return => dp 에 저장
   answer 는 모든 지점을 다 지났을 때의 최솟값으로 update

dp 를 이용하려 했으나 시간 부족으로 실패...

다른 사람의 풀이

def solution(n, costs):
    ans = 0
    costs.sort(key = lambda x: x[2])
    routes = set([costs[0][0]])
    
    while len(routes)!=n:
        for i, cost in enumerate(costs):
            if cost[0] in routes and cost[1] in routes:
                continue
            if cost[0] in routes or cost[1] in routes:
                routes.update([cost[0], cost[1]])
                ans += cost[2]
                costs[i] = [-1, -1, -1]
                break
    return ans

kruskal algorithm 을 이용해야 한다...

costs 는 cost 값 기준으로 정렬
costs[0][0] 를 초기값으로 갖는 set 선언 => routes

모든 섬들이 routes 에 포함될 때까지 반복문 돌리기
둘 중 하나의 섬만 routes 에 있을 경우엔 나머지 섬도 routes 에 넣어주고
ans 에 cost 값 더해준 후, 다리를 지났다는 의미로 [-1, -1, -1] 로 변경

외우자!!!

---

단속카메라

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

내 풀이 - 실패

def solution(routes):
    answer = len(routes)
    
    ### 모든 지점마다 dic 값 생성 ###
    dic = {}
    for s, e in routes:
        dic[s] = set()
        dic[e] = set()
        
    ### points: 지점들만 저장 ###
    points = list(dic.keys())
    points.sort()
    
    ### 각 지점마다 찍히는 자동차들 저장 ###
    for i in range(len(routes)):
        l = points.index(routes[i][0])
        r = points.index(routes[i][1])
        for j in range(l, r+1):
            dic[points[j]].add(i)
    
    ### 카메라에 찍힌 자동차들에 대한 정보 이용 ###
    cars = {i for i in range(len(routes))}
    
    ...
    
    return answer

예시
{-20: {0}, 15: {0}, -14: {0, 1, 2}, -5: {0, 1, 3}, -18: {0, 2}, -13: {0, 1, 2}, -3: {0, 3}}

각 포인트마다 카메라에 찍히는 자동차들을 저장해서 최소한의 횟수를 찾으려 함
but 횟수 찾는 부분을 구현하지 못했다...

다른 사람의 풀이

def solution(routes):
    routes = sorted(routes, key=lambda x: x[1])
    last_camera = -30001

    answer = 0

    for route in routes:
        if last_camera < route[0]:
            answer += 1
            last_camera = route[1]

    return answer

routes 를 진출 지점을 기준으로 정렬

진입 지점의 값이 -30000 으로 정해져 있으므로 last_camera = -30001

last_camera 가 진입 지점 보다 작을 경우
=> 카메라에 찍히지 않는 범위 이므로 answer + 1 & last_camera update

외우자!!!