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

22942번: 데이터 체커

코드

import sys
n = int(input())
circle = []
stack = []
for i in range(n):
    inp = sys.stdin.readline().split()
    a = int(inp[0])-int(inp[1])
    b = int(inp[0])+int(inp[1])
    circle.append([a,i,0])   # x-r값과 x+r값을 각각 원 번호와 함께 스택에 저장해준다. 
    circle.append([b,i,1])   # 처음인지 끝인지 확인하기 위해 0 또는 1을 추가해줬다.
circle.sort()

for i in range(n):
    fir = circle[i][2]
    if fir == 0:
        stack.append(circle[i])
    else:
        if stack[-1][2] == 0:  # 전 원이 닫히지 않은 상태이면
            if stack[-1][1] == circle[i][1]:    #원 번호가 같으면
                stack.pop()
            else:               #원 번호가 다르면 NO를 출력해준다.
                print("NO")
                exit(0)

print("YES")

 

설명

스택을 이용해서 괄호문제와 비슷하게 풀어봤다. 

먼저 원의 정보를 입력받아 원의 맨 앞(x-r)과 맨 뒤(x+r) 값을 구해준다. 각각을 a, b 변수에 저장해주고 [a,i,0], [b,i,1]과 같이 원의 번호와 맨 앞인지 맨 뒤인지 알려주는 0 또는 2을 같이 circle에 넣어준다.

circle을 정렬시켜주고 for문을 이용하여 만약 현재 들어온 것이 원의 맨 앞이면(circle[i][2] == 0 이면) 스택에 push를 해준다. 만약 맨 뒤의 정보이면 스택에 있는 마지막 부분의 원 번호를 현재 정보와 비교하여 같으면 pop을 해주고, 다르면 서로 다른 원끼리 교점이 존재하는 것이기 때문에 NO를 출력해준다.