책너두 - 알고리즘 챌린지[13/20]

오늘의 문제 : 데이터 체커

어제와 같은 스택 문제였다.

처음에는 모든 리스트를 2번 순회하려고 했더니, 역시 시간초과가 발생했었다.

원이 시작할 때와 끝날 때를 구분해서 스택에 넣어주면 시간내에 풀 수 있다.

다른 분들 풀이를 보니, 나는 start, end stack 2개를 활용했는데 처음부터 스택에 원의 반지름 + 원의 순서로 넣어주면 굳이 스택을 2개 사용할 필요가 없었다!

import sys

n = int(sys.stdin.readline().strip())
circles = []
for _ in range(n) :
    x, r = map(int, sys.stdin.readline().split())
    circles.append([x-r, x+r])

circles.sort(reverse=True)
start_stack = []
end_stack = []
while circles :
    start, end = circles.pop()
    if start_stack :

        while end_stack and start > end_stack[-1] :
            start_stack.pop()
            end_stack.pop()

        if end_stack and end >= end_stack[-1] :
            print("NO")
            exit()
        else :
            start_stack.append(start)
            end_stack.append(end) 

    else :
        start_stack.append(start)
        end_stack.append(end)
print("YES")