[프로그래머스] 요격 시스템 - 181188

문제 링크

🤔 Thinking

시간표 같은 그림이 있어 뭔가 그리디 알고리즘으로 접근하면 될 것 같다라는 생각으로 접근했다.
얻어 걸린(?) 듯한 느낌이 있다. 어떤 알고리즘을 적용해야하는 지 고민하는 노력을 하자.

파이썬에서 sort() 사용시 중첩 리스트의 값까지 정렬을 수행하는 점을 이용했다.

시작점과 끝점이 중요한데, shot을 한 후 shot 한 line을 기중으로 중첩되는 line 중에서 가장 끝점이 작은 값을 기준으로 변경한다. 이후 다음 로직을 수행한다.

💻 Code

# 그리디 알고리즘
# 파이썬 정렬 -> 리스트 내의 작은 수로 정렬
# 1. shot 2. shot 기준 line의 끝점까지 모든 라인 생략 3. 끝점 부터 shot
def solution(targets):
    answer = 0
    
    targets.sort()
    shot = 0
    
    for start, end in targets:
        if start < shot:
            if end < shot:
                shot = end
        else:
            answer += 1
            shot = end
    
    return answer