데이터 체커(백준 22942번)

문제

원 이동하기 2 문제를 만들고 만든 데이터가 문제의 조건에 맞는지 확인하는 코드를 작성해야한다.

해당 문제의 데이터는 아래 조건들을 만족해야한다.

1. 모든 원의 중심 좌표는 $x$축 위에 존재해야 한다.

2. $N$개의 원 중 임의의 두 원을 선택했을 때, 교점이 존재하지 않아야 한다. 즉, 하나의 원이 다른 원 안에 존재하거나 외부에 존재한다.

데이터 형식은 원의 개수 $N$이랑 각 원의 중심$x$좌표, 원의 반지름 $r$만 주어진다. 따라서, 2번 조건을 만족하는지만 확인하면 된다.

주어진 데이터가 해당 조건을 만족하는지 확인해보자.

나의 풀이(정답 참고)

import sys
N=int(input())

stack=[]
for i in range(N):
    x,r=map(int,sys.stdin.readline().strip().split())
    stack.append((x-r,i))
    stack.append((x+r,i))
stack.sort()
ans=[]
for s in stack:
    if ans:
        if ans[-1][1]==s[1]:
            ans.pop()
        else:
            ans.append(s)
    else:
        ans.append(s)
  
if ans:  
    print('NO')
else:
    print('YES')

• 원의 양 끝 점을 ‘(’, ‘)’ 이러한 괄호라고 생각하면 편하다. ‘(())’ 이런 괄호는 원래 문제가 없지만, 원으로 따졌을 때, $(_a(_b)_a)_b$ 이렇게 a, b 두 종류의 괄호(원)이 있다고 했을 때, 만나는 점이 생기는 것이다.
• 따라서 stack을 사용하여 문제를 풀었다.
  • 의문이 드는 것은, 원이 한점에서 만나는 것은 고려하지 않은 것 같은데, 정답 처리가 되었다는 것이다. 나중에 더 알아봐야 한다.