[ 백준 22942 해설 ] ( python ) 데이터 체커

 

📚 데이터 체커

 

문제

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

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

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

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

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

 

입력

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

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

 

출력

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

 

제한

•  2≤N≤200,000$2 ≤ N ≤ 200,000$ 
•  −1,000,000≤x≤1,000,000$-1,000,000 ≤ x ≤ 1,000,000$ 
•  1≤r≤10,000$1 ≤ r ≤ 10,000$ 
•  x,r$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

 

힌트

두 원의 위치관계

두 원의 위치관계를 파악할 때 아래를 이용하면 된다.

원 A의 반지름은 rA$r_A$, 원 B의 반지름은 rB$r_B$, 원 A와 원 B의 중심 사이의 거리를 d$d$라고 가정하자.

 

두 점에서 만난다.	한 점에서 만난다.		만나지 않는다.
	외접	내접	외부에 있는 경우	내부에 있는 경우	동심원
|rA−rB|<d<rA+rB$|r_A-r_B|<d<r_A+r_B$	rA+rB=d$r_A+r_B=d$	|rA−rB|=d$|r_A-r_B|=d$	rA+rB<d$r_A+r_B<d$	d<|rA−rB|$d<|r_A-r_B|$	d=0$d=0$

 

두 점 사이의 거리

 (x1,y1)$(x_1, y_1)$와 (x2,y2)$(x_2, y_2)$ 사이의 거리 d$d$를 구하는 식은 아래와 같다.

 d=(x1−x2)2+(y1−y2)2$d = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ 

 

 

 

 

✍ 접근

• stack
• 처음에는 원의 최하점, 최고점, 현재 max원을 사용해서 풀려고 했었다

 

 

 

정답코드

# ✨ 입력
import sys
input = sys.stdin.readline
N = int(input())
circle = []

# ✨ 준비
for i in range(N):
    a,b = map(int,input().split())
    circle.append((a-b,i))
    circle.append((a+b,i))
    
circle.sort()

# ✨ 비교
stack = []
for i in range(N*2):
    d, c = circle[i]
    if len(stack)==0:
        stack.append(circle[i])
    elif stack:
        if stack[-1][1] == c:
            stack.pop()
        else:
            stack.append(circle[i])
else:
    if len(stack) == 0:
        print('YES')
    else:
        print('NO')

해설

입력

• 문제에서 나온 값을 입력받는다

준비

• circle에 원이 x축과 만나는 두 점을 원의 idx와 함께 넣어준다
  => 원의 idx(i)를 함께 넣어주는 이유는 이따 stack에서 pop 할 때 같은 원인지 확인하기 위함

비교

• for로 N*2까지 돌린다.
  => N*2까지 돌리는 이유 : x축과 만나는 '두 점'을 넣어줬기 때문에
  • stack에 아무것도 없을 경우 append
  • stack에 값이 있을 경우, 현재 원의 idx와 비교한 후 pop한다
  • 현재 원의 idx와 stack[-1] 원의 idx가 다를 경우 append해준다
• for-else문으로 결과를 출력해준다

 

 

 

 

 

⭐ 배움

• 수학적으로 생각해서 해결하기 보다는 자료구조나 알고리즘을 먼저 생각해두고 해결하는 것이 더 빠른 해결 방법!