[백준] 22942번 - 데이터 체커 Python

문제

---

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

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

1. 모든 원의 중심 좌표는 $x$축 위에 존재해야 한다.
2. $N$개의 원 중 임의의 두 원을 선택했을 때, 교점이 존재하지 않아야 한다. 즉, 하나의 원이 다른 원 안에 존재하거나 외부에 존재한다.

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

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

입력

---

첫 번째 줄에는 원의 개수 $N$이 주어진다.

두 번째 줄부터 $N+1$번째 줄까지 원의 중심 $x$좌표, 원의 반지름 $r$이 공백으로 구분되어 주어진다.

출력

---

데이터가 조건에 맞는다면 YES, 조건에 만족하지 않는다면 NO를 출력한다.

제한

---

1.  $2 ≤ N ≤ 200,000$ 
2. $-1,000,000 ≤ x ≤ 1,000,000$ 
3. $1 ≤ r ≤ 10,000$ 
4.  $x, r$은 정수

예제 입력 1

---

4
5 4
3 1
6 1
13 3

예제 출력 1

---

YES

예제 입력 2

---

4
3 1
4 1
5 1
6 5

예제 출력 2

---

NO

풀이

---

import sys

input = sys.stdin.readline


class Point:
    def __init__(self,p,isOpen,no):
        self.p = p
        self.isOpen = isOpen
        self.no = no

def sol():
    n = int(input())
    c = []
    for i in range(n):
        x,r = map(int,input().rstrip().split())
        c.append(Point(x-r, True,i))
        c.append(Point(x+r,False,i))

    c.sort(key=lambda x : x.p)
    stack = []
    marked = set()
    for circle in c:
        cc = circle
        if cc.p in marked:
            print('NO')
            return
        if cc.isOpen:
            stack.append(cc)
            marked.add(cc.p)
        elif stack[-1].no != cc.no:
            print('NO')
            return
        else:
            marked.add(cc.p)
            stack.pop()
    print('YES')

if __name__=="__main__":
    sol()

정리

---

• x,r을 이용해 start, end를 여는 괄호, 닫는 괄호로 생각하면 된다.
• (x-r,open,원 번호), (x+r,close,원 번호) 형태로 모드 저장 후 좌표(x)를 기준으로 정렬한다.
• 이후 스택에 넣으면서 같은 원이 들어오면 pop 다른 원이 들어오는데 이전 원이 open 상태이고, 들어올 원이 close 상태이면 두 원이 겹치는 구간이 발생하므로 NO를 출력한다.

참고

---

https://velog.io/@dadahee/%EB%B0%B1%EC%A4%80-22942