백준 22942번 데이터체커 (python)

Problem

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

Solution

import sys

N = int(sys.stdin.readline())
c_list = list()
for _ in range(N):
    x, r = map(int, sys.stdin.readline().split())
    c_list.append((x, r))

def check():
    for i in range(N-1):
        for j in range(i+1, N):
            x1, r1 = c_list[i]
            x2, r2 = c_list[j]
            d = abs(x1 - x2)
            if not(r1 + r2 < d or d < abs(r1-r2)):
                return "NO"

    return "YES"

print(check())

브루트 포스를 이용한 풀이. $O(n^2)$이므로 시간초과

import sys

N = int(sys.stdin.readline())
c_list = list()
for _ in range(N):
    x, r = map(int, sys.stdin.readline().split())
    c_list.append((x-r, x))
    c_list.append((x+r, x))
c_list.sort()

def check():
    stack = []

    for c in c_list:
        if stack and stack[-1][1] == c[1]:
            stack.pop()

        else:
            stack.append(c)

    if stack:
        return "NO"
    else:
        return "YES"
    
print(check())

괄호를 응용한 풀이. 괄호와 마찬가지로 원의 x축과 만나는 점을 각각 (, )라고 하자.

(c1 , (c2, )c2, )c1 순서대로 나온다면 이는 만나지 않는 원이다.

(c1, (c2, )c1, )c2로 나온다면 이는 교점이 생기는 원이라고 볼 수 있다.

이 방식을 활용하면 O(n)으로 풀이할 수 있다.

Reference

https://velog.io/@leetaekyu2077/Python-백준-22942번-데이터-체커