[프로그래머스] 요격 테스트

😎 코딩테스트 연습>연습문제>요격 시스템

📘 문제풀이

from collections import deque 
def solution(targets):
    answer = 0
    interception = deque()
    targets.sort()
    for t in targets:
        st, et = t
        n = len(interception)
        while n >= 0:
            if n == 0:
                interception.append((st, et))
                break
                        
            s, e = interception[n-1]

            if s <= st < e or s < et <= e:
                if s <= st < et <= e:
                    interception.pop()
                    interception.append((st, et))
                elif s <= st:
                    interception.pop()
                    interception.append((st, e))
                else:
                    interception.pop()
                    interception.append((s, et))
                break
            n -= 1
            
                
    return len(interception)

굉장히 비효율적인 방법이었지만...ㅎㅎ
큐를 만들어서 겹치는 구간이 있는 타켓은 합치고 아니면 추가하는 방식을 사용했다. 
처음엔 n을 0부터 시작했는데 답은 맞았지만 시간초과 오류가 나서
끝에서부터 추가하는 방식으로 바꿨다.