📒문제

📒풀이

✔️시도

문제를 딱 보고 나서는 처음으로 든 생각

완전탐색은 안되겠네

입력의 범위가 너무 커서, 하나를 기준으로 먼저 지워보면서 진행할 수가 없었다.

또, 가장 많이 겹치는 선분부터 지우려고 해도 다른 선분과 가장 많이 겹치는 선분을 지울 때

요격 위치를 기준으로 선분을 지울 수 있기 때문에 겹치는 선분들이 모두 지워진다는 보장이 없다.

✔️해결

선분들을 우선 가장 빨리 끝나는 순으로 정렬한다.

끝점을 기준으로 요격하여 선분을 지운다고 생각하면 된다.

첫 선분의 끝 점을 현재 요격 지점으로 지정하고, 그 다음 선분을 살펴볼 때,

다음 선분의 시작점이 현재 요격 지점보다 먼저 시작한다면, 현재 요격 지점으로 다음 선분도 지울 수 있다.

다음 선분의 시작점이 현재 요격 지점보다 먼저 시작하지 않는다면, 새로운 요격 지점이 필요하기 때문에 요격 지점의 갯수와 현재 요격 지점을 다음 선분의 끝 점으로 업데이트 해준다.

def solution(targets):
    # targets 정렬
    targets.sort(key=lambda ele: ele[1])
    cnt, end = 0, 0
    for target in targets:
        if target[0] >= end:
            cnt += 1
            end = target[1]
    
    return(cnt)

📒시간복잡도

O(len(targets))

📒정리

그리디 알고리즘을 사용하여 풀이를 하는 문제이다.

그리디 알고리즘은 각 문제의 특성을 파악하여 항상 최적의 해가 되는 쪽으로 나아가 정답을 찾는 알고리즘이다.

그리디 알고리즘은 볼 때마다 난해하다. 문제의 조건을 잘 보고, 언제가 최적인지, 어느 상황만 고려하면 최적인지, 어느 상황은 고려 안해도 되는지를 항상 추려내야 하기 때문이다.