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

문제

프로그래머스

 

풀이 아이디어

targets의 요소를 정렬하고 반복문을 사용해 순서대로 검사한다. 앞의 요소부터 순서대로 검사하며 연결이 끊길 경우 요격 회수를 하나 추가하고 다시 검사하는 식으로 진행한다. 

 

answer: 최소 요격 회수

min_line: 현재 겹쳐있는 영역들 중 가장 빨리 끝나는 지점의 위치 

 

if target[0]+1>min_line: 에서 +1을 해주는 이유는 영역이 겹쳐야 하기 때문. 예를 들어 [1,2], [2,3]의 경우 끝부분이 연결되어있지만 영역이 겹치지는 않는다. 겹치기 위해서는 한 쪽의 끝 부분보다 최소 1의 길이 앞에 있는 위치에 속해야 한다.   

 

 

코드 

from collections import deque 

def solution(targets):
    answer = 0 
    min_line = 0
    targets.sort()
    
    for target in targets:
        if target[0]+1 > min_line:
            answer +=1 
            min_line = target[1]
        elif target[1]<min_line:
            min_line = target[1]
        
    return answer