문제 설명

이번 포스팅은 백준 22942번: 데이터 체커 문제 풀이에 대한 기록입니다.

[ 입출력 예시 ]

문제를 간단히 요약하자면, "중심이 $x$축 위에 존재하는 원들의 중심 좌표와 반지름이 주어졌을 때, 서로 겹치는 원이 없는지를 체크하는 문제" 입니다.

풀이

1. 올바른 괄호 찾기를 떠올리자!

---

처음 이 문제를 접했을 땐, 문제에서 말하는 그대로 $x$축 위의 원들이 있는 모습을 떠올리며 접근했었습니다.

그러나 원의 여러 가지 위치 관계들을 생각하며 원들이 겹치는 경우를 따져보려고 하니 너무 복잡했고, 다른 방법이 있을 것이라 생각하고 고민했습니다.

그러다 stack을 이용해 올바른 괄호로 구성된 식을 판별하는 문제를 떠올리게 되었습니다.

"$(())()$" 와 같은 식이 있을 때,

"$($" 이 나오면 stack을 하나 늘리고, "$)$" 이 나오면 하나 줄여나가는 과정을 거친 후에

마지막에 stack이 비어있다면 괄호가 올바른 식, 그렇지 않으면 올바르지 않은 식이라고 판별할 수 있습니다.

이를 어떻게 이 문제에 적용할 수 있을까요?

각 원의 왼쪽 끝점을 $($ , 오른쪽 끝점을 $)$ 라고 생각해봅시다.

만약 어떤 원 $C_1$의 ( 가 나오고, 그 사이에 원 들의 $C_2$의 ( , ) 가 나와서 잘 닫힌 후에 $C_1$의 ) 가 나온다면 두 원은 겹치지 않는다고 할 수 있습니다.

그러나 $C_1$의 ( 이후에 $C_2$의 ( 가 나오고, $C_1$의 ) 가 먼저 나온다면 두 원은 서로 겹친다고 할 수 있습니다.

이런 식으로, "어떤 원의 왼쪽 끝점과 오른쪽 끝점 사이에 짝지어 지지 못한 다른 원의 왼쪽 끝점이 존재한다면 원이 겹친다" 라고 판단할 수 있는 것입니다.

2. 아이디어 구현하기

---

이제 stack을 이용해서 이를 구현하기만 하면 됩니다.

for i in range(N):
    x, r = map(int, sys.stdin.readline().split());
    circles.append((x-r, i))
    circles.append((x+r, i))    
circles.sort()

먼저 입력으로 들어온 중심 좌표, 반지름을 이용하여 각 원의 왼쪽, 오른쪽 끝점을 계산하여 저장해줍니다.

이때 각 점들이 어떤 원을 이루는 점인지 구분할 수 있어야 하기 때문에 원의 번호 i 도 함께 짝지어 튜플로 저장합니다.

이후 점들을 왼쪽부터 차례로 나열하기 위해 정렬해주어야 합니다.

stk = []
for c in circles:
    if stk:
        if stk[-1][1] == c[1]:
            stk.pop()
        else:
            stk.append(c)
    else:
        stk.append(c) 
        
if stk:
    print('NO')
else:
    print('YES')

이제 stack을 이용해 판별하면 됩니다.

점들을 왼쪽부터 차례로 보면서 stk에 push하고, stk의 top에 있는 점이 자기가 속한 원의 오른쪽 끝점을 만나면 pop됩니다.

만약 중간에 다른 원의 왼쪽 끝점이 push되면 그 점은 끝날 때까지 stk에서 나가지 못하게 됩니다.

따라서 for문이 종료된 후 stk에 남아있는 것이 있다면 겹치는 원이 하나 이상 존재한다는 의미이므로 'NO'를, 그렇지 않으면 'YES'를 출력하면 됩니다.

문제 해결!!

결과 코드

import sys

N = int(sys.stdin.readline())
circles = []

for i in range(N):
    x, r = map(int, sys.stdin.readline().split());
    circles.append((x-r, i))
    circles.append((x+r, i))    
circles.sort()

stk = []
for c in circles:
    if stk:
        if stk[-1][1] == c[1]:
            stk.pop()
        else:
            stk.append(c)
    else:
        stk.append(c) 
    
if stk:
    print('NO')
else:
    print('YES')