[문제해결 - 자료구조] BOJ22942 / 데이터 체커 / 골드4 (Python, 파이썬)

oldshoe·2025년 5월 24일

알고리즘

알고리즘 문제

목록 보기

38/51

백준22942 문제 보러 가기

문제

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

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

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

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

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

입력

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

출력

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

제한

$2 ≤ N ≤ 200,000$
$-1,000,000 ≤ x ≤ 1,000,000$
$1 ≤ r ≤ 10,000$
$x, r$ 은 정수

예제 입력 1

$2 ≤ N ≤ 200,000$

$-1,000,000 ≤ x ≤ 1,000,000$

$1 ≤ r ≤ 10,000$

$x, r$ 은 정수

예제 출력 1

YES

예제 입력 2

4
3 1
4 1
5 1
6 5

예제 출력 2

문제 해결 과정

처음에는 단순히 일단 주어진 힌트를 이용해서 수식을 통해 해결하려 했다.
이중 포문만 쓰면 단순하게 일단(?) 해결은 가능했다.

일단 시간 초과와는 관계없이 해결을 했다.

N = int(input())
x_list = []
r_list = []
check = 0
for _ in range(N) :
    x, r = map(int ,input().split())
    x_list.append(x)
    r_list.append(r)

for i in range(N) :
    for j in range(i+1, N) :
        if abs(r_list[i]-r_list[j]) <= abs(x_list[i]-x_list[j]) and abs(x_list[i]-x_list[j]) <= abs(r_list[i]+r_list[j]) :
            check = 1
            if check == 1 :
                print('NO')
                break
                
    if check == 1 :    
        break

if check == 0 :
    print('YES')

역시나 시간 복잡도 N^2으로 시간초과에 걸렸다.
그러면 다른 방법을 생각해야하는데, 어떤 자료구조를 이용해서 해결해야 할지 생각이 나지 않았다.
참고 블로그를 찾아서 참고했다.

지난 번에 해결했던(블로그를 참고하긴 했지만) '괄호의 값' 문제와 유사한 문제였다.
원은 x축 위에만 있기 때문에 각 끝점과 인덱스를 튜플로 저장을 하여 x축과 원의 교점을 기준으로 오름차순 정렬을 한다.
5 4를 예로 보면 왼쪽 끝점은 1이되고 오른쪽 끝점은 9가 된다.
이것을 괄호라고 생각해보자. 겹치지 않으려면 (()) 이런 형태로 저장이 되는데, ) 닫힌 괄호가 나왔을 때 전의 것이 본인의 인덱스여야한다.
(그래서 각 끝점과 인덱스를 튜플로 저장을 한다.)

그래서 열린 괄호 ( 가 나왔을 때마다 stack에 저장을 하고, 닫힌 괄호 )가 나왔을 때는 이전에 담긴 열린 괄호가 자신의 것인지 확인을 하고 그럴 때마다 pop을 해준다.
결국 모든 원을 확인했을 때 stack에 남아있으면 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')