[프로그래머스][그리디] 요격 시스템

• 요격 시스템

프로그래머스

 

• 내 풀이
  • 끝점 기준으로 정렬 해야함
  • 처음에 시작지점 기준으로 해서 틀림
    • 시작점 기준으로 정렬하면 안되는 이유: 반례 [[1, 10], [2, 3], [3, 4], [4, 5]]
    • 시작점이 제일 빠른 미사일이 끝점도 제일 끝이게 되면 10을 기준으로 뒤에 오는 미사일 2,3,4를 다 하나로 처리해버림
      
      • [1,10]이랑만 겹칠뿐 나머지 3개끼리는 겹치지 않는 대도 한번에 처리하는걸로 계산된다
  • 다음 미사일이 끝지점보다 크거나 같아질때까지 인덱스를 넘겨버림

def solution(targets):
    answer = 0
    targets.sort(key=lambda x:x[1])
    i=-1
    while i<len(targets)-1:
        i+=1
        target=targets[i]
        
        while i+1<len(targets) and target[1]>targets[i+1][0]:
            i+=1
        answer+=1
    
    return answer

 

• 다른 사람 풀이 
  • 끝점과 시작점 비교하는건 같지만 구현이 조금 다름

끝점 기준으로 정렬

• 끝지점에서 쏜다고 생각
  • 각 미사일을 하나씩 보면서 그리디하게 쏠건지 안쏠건지 확인할 수 있음
• • 끝지점이 더 뒤인 미사일이라도 앞에 나온 미사일보다 시작지점이 앞이면 앞에서 처리가능

def solution(targets):
    answer = 0
    targets.sort(key = lambda x:[x[1],x[0]])
    
    s,e = 0,0 
    for x in targets:
        if x[0]>=e:
            e = x[1]
            answer += 1
    return answer