[Python] 백준 22942 - 데이터 체커 문제 풀이

Boo Sung Jun·2022년 3월 24일
0

알고리즘, SQL

목록 보기
55/70
post-thumbnail

Overview

BOJ 22942번 데이터 체커 Python 문제 풀이
분류: Data Structure (자료구조)


문제 페이지

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


풀이 코드 1

from sys import stdin


def main():
    def input():
        return stdin.readline().rstrip()

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

    circles.sort()
    stack = []
    crds = set()
    for crd, i, flag in circles:
        if crd in crds:
            print("NO")
            return
        if flag == 0:
            stack.append((crd, i))
        elif stack[-1][1] != i:
            print("NO")
            return
        else:
            crds.add(crd)
            stack.pop()
    print("YES")


if __name__ == "__main__":
    main()

괄호 매칭 문제와 같이 스택을 이용해서 풀이한다. 원과 x축의 2개 교점 중에서 왼쪽은 여는 괄호, 오른쪽은 닫는 괄호라고 생각한다. 단, 이 문제에서는 원의 접점이 존재하는지와 매칭된 괄호가 동일한 원의 것인지를 판단해야 하기 때문에 더 까다롭다.


참고자료

https://velog.io/@dadahee/%EB%B0%B1%EC%A4%80-22942

0개의 댓글