[Python][백준] 22942번 데이터 체커

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

공부 날짜 : 2023.01.17
정답 참조 여부 : O

x축위에 반지름 r인 원이 놓일 때 각 원이 겹치는지 여부를 판단하는 문제이다.

---

스택이라는 구조를 어떻게 활용하는건지 이해할 수 있었던 문제였다.

처음에는 -101만 ~ 101만의 배열을 만들고 그 위에 원이 놓여있다를 표시하는식으로 문제를 풀었는데 79%에서 시간초과가 나왔다.

다른 방법이 도저히 떠오르지 않아 정답을 참고했다. 처음엔 정답을 봐도 이해를 못했는데 스택이라는 구조를 생각하며 문제를 풀다보니 원이 열리고 닫히는게 괄호와 유사하다는 점에서 스택과 비슷하다는걸 이해했다.

문제를 푼 방법은
원의 시작점과 끝점, 원의 종류, 시작점인지, 끝점인지 구분해서 리스트로 만들엇다.

circle[*] = [point, circle_num, check = 1 if start else 0]

그런다음 point를 기준으로 sort를 해준뒤 앞의 점과 비교하며 같으면 NO, 원이 끝점일때 스택의 마지막으로 열린 원이 다른 원이면(? 나도 글로 쓰니까 이해가 안되네) 겹침으로 처리했다.

+그런데 외접하는 모든 경우를 생각하지 않았는데 정답이라고 나왔다....
지금 밑의 코드는 왼쪽 내접인 경우는 체크햇지만 왼쪽에서 외접, 오른쪽에서 외접,내접인 경우에 NO가 나와야 하지만 YES가 나오는 코드이다
백준에서 20년 3월에 오타 수정게시글을 올리지 말아달라는 공지가 올라왔고, 21년 4월 이후로 이러한 사항에 대해서 수정을 하지 않는다고 공지를 했다. 게시일인 23년 1월 17일기준 정답으로 나왔지만 추후 수정되고 나면 틀렸습니다라고 나올것이다.

소스코드

import sys
input = sys.stdin.readline
###########################################
n = int(input())

circle = []

for circle_num in range(1, n+1):
    x, r = map(int, input().split())
    
    circle.append([x - r, circle_num, 1])
    circle.append([x + r, circle_num, 0])
    
circle.sort()

stack = [[None,None]]

for point, num, check_ in circle:
    if point == stack[-1][0]:
        print("NO")
        break

    if check_ == 1:
        stack.append([point, num])
    else:
        if stack.pop(-1)[1] != num:
            print("NO")
            break

else:
    print("YES")