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

문제 링크

https://www.acmicpc.net/problem/22942

22942번: 데이터 체커

 

문제 풀이

처음에는 원을 모두 입력받아서 정직하게 외부에 있는지, 내부에 있는지 반지름끼리 더하고 빼고 중심사이의 거리를 비교해서 풀이했는데, 시간 초과가 떴다. 그래서 다른 블로그의 아이디어를 참고해서 풀었는데, 그래도.. 시간 초과가...

어쨌든 마지막에 import stdin 이 부분만 추가해주니 해결되었다! 그냥 input()으로 받아선 안되나보다..

1. 원을 입력 받을 때, 리스트에 x축 위에 있는 양 끝점 정보를 넣어준다.
   1. (x-r, x, 0) = (중심에서 반지름을 뺀 왼쪽 점, 중심, 왼쪽 표시)
   2. (x+r, x, 1) = (중심에서 반지름을 더한 오른쪽 점, 중심, 오른쪽 표시)
2. 리스트의 첫번 째 요소인 왼쪽 점을 기준으로 정렬한다.
3. 리스트를 순회하면서 원이 겹치지 않는지 확인한다.
   1. 왼쪽인 경우에는 스택에 추가한다.
   2. 오른쪽이라면  현재 스택에 있는 가장 마지막 요소의 중심 x와 같은지 확인하고, 같지 않다면 원이 겹치고 있기 때문에 "NO"를 출력한다.
   3. 위 조건에 걸리지 않고 모두 순회했다면 "YES"를 출력한다.

 

전체 코드

from sys import stdin
n = int(input())

circles = []
stack = []

for _ in range(n) :
    x, r = map(int, stdin.readline().split())
    circles.append((x-r, x, 0))
    circles.append((x+r, x, 1))

circles.sort()

for i in range(len(circles)) :
    if circles[i][2] == 0 :
        stack.append(circles[i][1])
    elif circles[i][2] == 1 :
        if circles[i][1] == stack.pop() :
            continue
        else :
            print("NO")
            exit(0)

print("YES")