요격 시스템

 

코딩테스트 연습 - 요격 시스템 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

나의 풀이

# 2024-07-18
def solution(targets):
    answer = 0
    targets = sorted(targets, key=lambda x:(x[1],x[0]))
    
    bomb_point = 0
    for start,end in targets:
        if bomb_point<=start:
            answer+=1
            bomb_point=end
    
    return answer

 

시간복잡도

sorted정렬 : 선형로그 시간 복잡도
for start, end in targets : 선형 시간 복잡도

즉, 해당 알고리즘의 시간복잡도는 선형로그 시간 복잡도 ( O(nlogn) )