1 minute read

1. 데이터 체커

  • 원 이동하기 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$은 정수

풀이

# your code goes here

import sys

# 첫 번째 줄에는 원의 개수 N이 주어진다.

N = int(sys.stdin.readline())

dic = {}
arr = []

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

flag = True

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

    if not arr:
        arr.append((x,r))
        dic[str(x+r)] = x+r
        dic[str(x-r)] = x-r
    else:
        if str(x+r) in dic.keys() or str(x-r) in dic.keys():
            flag = False
            break
        else:
            for x1, r1 in arr:
                if r1 ** 2 + r ** 2 == (x1-x) ** 2:
                    flag = False
                    break
                elif r1 == r and abs(x1-x) == r:
                    flag = False
                    break
            if not flag:
                break

        arr.append((x,r))
        dic[str(x + r)] = x + r
        dic[str(x - r)] = x - r

print('YES' if flag else 'NO')

채점 결과

  • 오답(시간 초과)

리뷰

  • 두 원의 거리를 비교($r_1^2 + r_2^2$과 $(x_1-x_2)^2$를 비교하는것)하는 기하학적 지식을 요하는 부분은 통과했다.

  • 시간 단축을 위해 원이 접할경우 즉시 NO를 출력시키는 방식으로 진행하였다.

  • 임의의 두 원을 골라 비교하는 부분에서 시간 복잡도 문제가 발생한다.

    • 데이터 개수는 최대 200,000개. $_{200000}C_2$는 약 200억가지의 경우의 수가 도출된다.

이 문제의 알고리즘 분류

  • 자료구조
  • 정렬
  • 기하학
  • 스위핑
  • 스택