Overview
BOJ 22942번 데이터 체커 Python 문제 풀이
분류: Data Structure (자료구조)
문제 페이지
https://www.acmicpc.net/problem/22942
풀이 코드 1
from sys import stdin
def main():
def input():
return stdin.readline().rstrip()
n = int(input())
circles = []
for i in range(n):
x, r = map(int, input().split())
circles.append((x - r, i, 0))
circles.append((x + r, i, 1))
circles.sort()
stack = []
crds = set()
for crd, i, flag in circles:
if crd in crds:
print("NO")
return
if flag == 0:
stack.append((crd, i))
elif stack[-1][1] != i:
print("NO")
return
else:
crds.add(crd)
stack.pop()
print("YES")
if __name__ == "__main__":
main()
괄호 매칭 문제와 같이 스택을 이용해서 풀이한다. 원과 x축의 2개 교점 중에서 왼쪽은 여는 괄호, 오른쪽은 닫는 괄호라고 생각한다. 단, 이 문제에서는 원의 접점이 존재하는지와 매칭된 괄호가 동일한 원의 것인지를 판단해야 하기 때문에 더 까다롭다.
