[python]22942_데이터 체커

1 걸린 시간 : 1h

2 사용한 자료구조 및 개념 : deque, sort

---

💡 문제풀이 아이디어 및 어려웠던 점

---

💫 아이디어

 

1️⃣ 각 원의 중심 좌표와 반지름을 활용하여 시작점과 끝점을 구한다.

2️⃣ 하나의 원이므로 튜플 형태( 시작점, 끝 점 )로 리스트에 담는다.

3️⃣ sort를 활용하여 시작점을 기준으로 정렬한다.

→ 가장 왼쪽에 위치한 원부터 차례로 검사할 수 있어 확인 과정이 수월해진다.

4️⃣ stack 최상단 원의 끝점이 현재 원의 시작점(start)보다 작다면, 이는 겹치지 않음을 뜻하므로 스택의 원 끝점을 pop한다.

예를 들어 스택에 [9, 4]가 있고 현재 비교하는 원이 (5, 7) 이라면 스택의 최상단 원의 끝점 4는 현재 비교하는 원의 시작점 5보다 작으므로 겹치지 않음을 뜻한다. 따라서 4 를 스택에서 제거한다.

5️⃣ 스택에 원이 남아 있다면, 스택 최상단 원의 끝점과 현재 비교하는 원의 시작점과 끝점 사이에 있는지 확인하다. 사이에 있다면 겹치는 경우이므로 False를 반환하고 확인함수를 종료한다.

예를 들어 스택에 4가 pop되어 [ 9 ] 만 남아있는 상태이다. 스택에 원이 존재하니 원의 끝점 9이 현재 비교하는 원(5, 7)의 시작점과 끝점 사이에 존재하는지 확인한다. 사이에 존재하지 않으니 조건문에서 걸리지 않는다.

그러나 case2에서 스택에 [ 11, 4 ] 가 있고 현재 비교하는 원이 ( 3, 5 ) 일 때, 3과 5 사이에 4가 존재하게 되는 것이므로 원이 겹치게 된다. 따라서 False를 반환하고 함수를 종료하여 NO가 출력된다.

6️⃣ 위의 두 조건문에 해당하지 않으면 다음 비교를 위해 현재 원의 끝점을 스택에 추가한다.

 

 

case 1

 

---

👻 어려웠던 점

 

🚨 아이디어 생각하는게 힘들었던 문제…! 검색 찬스를 썼다

 

---

Solution Code & 주석

from collections import deque
from sys import stdin

def check():
    stack = deque()
    for start, end in circle:
        while stack and stack[-1] < start:
            stack.pop()
        if stack:
            if start <= stack[-1] <= end:
                return False
        stack.append(end)
    return True

circle = []
n = int(stdin.readline())
for i in range(n):
    center, radius = map(int, stdin.readline().split())
    circle.append((center - radius, center + radius))
circle.sort()  # [ (1, 9), (2, 4), (5, 7), (10, 16) ]

if check():
    print('YES')
else:
    print('NO')