[프로그래머스] 고득점Kit (6) - 그리디(2) (파이썬)

1. 구명보트 (Lv. 2)

# 구명보트
def solution(people, limit):
    people.sort(reverse=True)
    answer = 0
    i = 0
    j = len(people) - 1
    while i <= j:
        if people[i] + people[j] <= limit:
            j -= 1
        answer += 1
        i += 1
    return answer

 

투 포인터를 이용했다.

내림차순으로 정렬을 하고, i와 j를 각각 처음과 끝 인덱스 값으로 초기화

people[i]와 people[j]의 합이 limit이하라면 j -= 1

i += 1, answer += 1

---

2. 섬 연결하기 (Lv. 3)

# 섬 연결하기
import heapq


def solution(n, costs):
    arr = [[]for _ in range(n)]
    for x, y, cost in costs:
        arr[x].append((cost, y))
        arr[y].append((cost, x))
    answer = prim(n, arr, 0)
    return answer


def prim(n, arr, start):
    result = 0
    visited = [False] * n
    q = []
    heapq.heappush(q, (0, start))
    while q:
        cost, node = heapq.heappop(q)
        if not visited[node]:
            visited[node] = True
            result += cost
        for ncost, nnode in arr[node]:
            if not visited[nnode]:
                heapq.heappush(q, (ncost, nnode))
    return result

 

힙 자료구조, 프림알고리즘을 이용해서 간단하게 풀 수 있었다.

프림 알고리즘은 현재 노드들과 연결된 모든 값들을 힙에 넣어주면서 연결해 나가는 알고리즘이다.

---

3. 단속카메라 (Lv. 3)

# 단속카메라
def solution(routes):
    routes.sort(key=lambda x: x[1])
    now = -30000
    answer = 0
    for start, end in routes:
        if now < start:
            answer += 1
            now = end
    return answer

 

고민을 오래 할 뻔했으나 그림 한 번 그리면서 바로 알아냈다.

모든 차의 이동 경로를 끝나는 시기가 빠른 순서로 정렬을 하고

앞에서부터 각 end 지점 마다 카메라를 설치해준다.

If (해당 이동 경로의 시작) <= (현재 카메라를 설치한 곳), end 지점에 카메라 설치 없이 continue