BOJ [데이터 체커]

문제

2022-03-24

문제보기

일직선위에 원이 여러개 주어지는데 만나는 원이 있는지 알아보라.

풀이

x-r, x+r 두 포인트를 주목하자. 같은 원의 두 포인트를 각각 여는 괄호, 닫는 괄호 라고

생각하면 쉽게 풀린다.

(x-r, 여는괄호, 원번호)

(x+r, 닫는괄호, 원번호)

이렇게 리스트에 다 저장하고 x좌표 순으로 오름차순으로 정렬한 뒤에 괄호 문제 풀듯이

같은 괄호로 () 되면 stk에서 지우고 다른 괄호로 () 하면 '실패' 처리하면 된다.

코드

n = int(input())

circles = []
for _ in range(n):
    circles.append(list(map(int,input().split())))

points = []
check_point = []

stk = []
is_no = False

for i in range(len(circles)):
    points.append([circles[i][0]-circles[i][1],1,i])
    points.append([circles[i][0]+circles[i][1],0,i])
    check_point.append(circles[i][0]-circles[i][1])
    check_point.append(circles[i][0]+circles[i][1])

if len(set(check_point)) != len(check_point):
    is_no = True

points.sort()

if is_no == False:
    for point in points:
        if point[1] == 0:
            if point[2] == stk[-1][2]:
                stk.pop()
                continue
            else:
                is_no = True
                break
        else:   
            stk.append(point)

if not is_no:
    print('YES')
else:
    print('NO')