문제

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

난이도

GOLD 5

풀이

틀린 내용 지적 환영합니다.

시도한 풀이

코드

# 시간 초과 - 모든 원 조합을 보는 방법
import sys
input = sys.stdin.readline
def solution(n):
    # 데이터 입력
    circles = set()
    for i in range(n):
        x, r = map(int, input().split())
        # 중복 방지
        if (x, r) in circles:
            return "NO"
        circles.add((x, r))
    
    # 문제
    ordered = sorted(circles, key=lambda x: x[0])
    p = 0
    for i in range(n):
        rA = ordered[p][1]
        rB = ordered[i][1]
        d = ordered[p][0] - ordered[i][0]
        # 외부
        if rA + rB < d:
            p = i
        # 외접
        if rA + rB == d:
            return "NO"
        # 내접 or 교차
        if  d == abs(rA - rB) or rA + rB > d > abs(rA - rB):
            return "NO"
        # 내부
        if d < abs(rA - rB):
            p = p if (rA > rB) else i
    return "YES"

아이디어

• 기본 아이디어: 중심의 x좌표가 작은 순서부터 원의 조합을 살피기
• 단, 단순히 한 원의 좌우만 보면 안 됨 -> 좌우 원은 작더라도 이후 원이 훨씬 커서 현재 원과 교차 혹은 접점이 생길 수 있음
• 시도: 모든 원의 조합을 살펴봄

소요 시간

32분 정도

결과

시간 초과 (못품)

---

수정한 풀이

참고

https://ongveloper.tistory.com/420

코드

# stack 이용
import sys
input = sys.stdin.readline

class Point:
    def __init__(self, p, isOpen, no):
        self.p = p
        self.isOpen = isOpen
        self.no = no

def solution(N):
    circles = []

    for i in range(N):
        x, r = map(int, input().split())
        # (point, isOpen, circleNo)
        circles.append(Point(x - r, True, i)) # == 여는 괄호
        circles.append(Point(x + r, False, i)) # == 닫는 괄호
    
    circles.sort(key=lambda x: x.p)
    stack = []
    for i in range(2*N):
        next = circles[i]
        current = stack[-1] if stack else next
        # same circle: open & close
        if current.no == next.no and current.isOpen and not next.isOpen:
            stack.pop()
        else:
            # 기존 원이 열리기 전 다른 원이 닫힐 때
            # 즉, 겹치거나 교차할 때
            if current.isOpen and not next.isOpen:
                print("NO")
                return
            # 원 정보를 스택에 추가
            stack.append(next)
    print('YES')

if __name__ == "__main__":
    N = int(input())
    solution(N)

아이디어

• 기본 아이디어: 원의 좌우 양끝단을 스택에 넣고 빼며 교차 여부 검증 like 괄호문제
• 클래스: 원의 양끝단 지점 - x좌표, 개폐 여부, 원의 번호
• pop 조건: 동일한 원이고, current가 open, next가 closed일 경우 (** empty 스택일 경우 next와 current가 동일하기 때문에 개폐여부까지 검사)
• 교차할 경우(current가 open, next가 다른 원의 close) 조건을 만족하지 않기 때문에 바로 리턴
• 쩐다...

궁금증

• 내접하는 경우도 모든 처리가 가능한가? -> 입력 순서에 따라 케바케 -> 안됨
• !!! 좌표에 따라 정렬 -> 운좋게 동일 원이 먼저 pop되었을 경우 내접/외접 케이스를 잡을 수 없음
• 처리 못하는 예시

  2
  3 1
  2 2

  단, 아래와 같은 경우는 정상적으로 NO 출력

  2
  2 2
  3 1

최종 풀이

import sys
input = sys.stdin.readline

class Point:
    def __init__(self, p, isOpen, no):
        self.p = p
        self.isOpen = isOpen
        self.no = no

def solution(N):
    circles = []

    for i in range(N):
        x, r = map(int, input().split())
        # (point, isOpen, circleNo)
        circles.append(Point(x - r, True, i)) # == 여는 괄호
        circles.append(Point(x + r, False, i)) # == 닫는 괄호
    
    circles.sort(key=lambda x: x.p)
    stack = []
    marked = set()
    for circle in circles:
        next = circle
        if next.p in marked: # 내외접
            print("NO")
            return
        if next.isOpen:
            stack.append(next)
            marked.add(next.p)
        elif stack[-1].no != next.no: # 교차
            print("NO")
            return
        else:
            marked.add(next.p)
            stack.pop()
    print('YES')
            
if __name__ == "__main__":
    N = int(input())
    solution(N)

# 복잡도: O(nlogn)(정렬) + O(n)(스택) + O(1)*n(집합) = O(nlogn)

아이디어

• 내외접 하는 경우 입력 순서에 따라 발생하는 예외 케이스 처리
• circles에 중복되는 좌표가 있으면 무조건 접하는 경우이므로 이를 처리하기 위해 set 사용
• 이미 존재하는 좌표일 경우 조건에 부합하지 않음

---

스택 쓸 생각을 도대체 어떻게 하지... 와 대박!