[백준] 22942
문제
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되었을 경우 내접/외접 케이스를 잡을 수 없음
- 처리 못하는 예시
단, 아래와 같은 경우는 정상적으로 NO 출력2 3 1 2 2
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 사용
- 이미 존재하는 좌표일 경우 조건에 부합하지 않음
스택 쓸 생각을 도대체 어떻게 하지... 와 대박!
Author And Source
이 문제에 관하여([백준] 22942), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dadahee/백준-22942저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)