[Python/파이썬] 백준 22942번 데이터 체커

22942번: 데이터 체커

문제

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

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

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

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

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

 

입력

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

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

출력

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

 

코드

import sys
input = sys.stdin.readline

n = int(input())
circle = []  # 원의 끝(왼쪽/오른쪽) 위치, 원이 왼쪽인지 오른쪽인지, 원의 번호
for i in range(n):
    x, r = map(int, input().split())
    left = x - r
    right = x + r
    circle.append([x-r, 0, i])    # 원의 왼쪽 끝, 왼쪽이라는 표시, 원 번호
    circle.append([x+r, 1, i])    # 원의 오른쪽 끝, 오른쪽이라는 표시, 원 번호

circle.sort()    # 원 좌표들 정렬

stack = []
prev_right = -10000000
for i in range(n * 2):
    if circle[i][1] == 0:   # 원의 왼쪽이 들어왔을 때
        if prev_right == circle[i][0]:  # 이전 원과 한 교점에서 만나는 경우
            print("NO")
            exit()
        stack.append(circle[i][2])  # 원의 번호를 스택에 append
    else:                   # 원의 오른쪽이 들어왔을 때
        if stack[-1] == circle[i][2]: # 지금 나온 원과 짝이 맞다면 다른 원 안에 잘 있는 것
            stack.pop()
            prev_right = circle[i][0]
        else:
            print("NO")    
            exit()

print("YES")    # 끝까지 안 걸리고 가면 모두 교점이 없는 것

1. 입력받은 원의 중심 좌표와 반지름을 이용하여 circle 배열에 [왼쪽/오른쪽 좌표, 왼쪽/ 오른쪽 표시, 원의 번호] 배열로 원의 왼쪽 끝과 오른쪽 끝을 저장해준다. 
2. 다 입력받은 후 circle 배열을 정렬해준다.
3. circle에 대해 순회하며 
   • 원의 왼쪽이 나왔을 때 : stack에 넣어줌
   • 원의 오른쪽이 나왔을 때 
     • stack의 top에 있는 원의 오른쪽이라면 다른 원의 안에 있는 것이므로 stack의 top을 pop해주고 넘어가면 된다. 이때 지금 원의 오른쪽 끝의 좌표를 prev_right 변수에 저장해주는데 이는 두 원이 한 점에서 만날 때를 확인하기 위해 저장하는 것이다.
     • stack의 top에 있는 원의 오른쪽이 아니라면 두 원이 두 점에서 만나고 있는 상황이므로 NO를 출력하고 프로그램을 종료시킨다
4. 프로그램이 중간에 종료되지 않는다면 어떠한 원도 만나지 않는 것이므로 YES를 출력해준다.