백준 : 데이터 체커 22942

백준 gold 4 : 데이터 체커 22942

문제 링크

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

실패 코드

def isMeet(x1, r1, x2, r2):
    d = abs(x1 - x2)
    
    if abs(r1-r2) < d < r1+r2:
        return True
    elif r1 + r2 == d:
        return True
    elif abs(r1-r2) == d:
        return True
    return False

n = int(input())
circles = []

for _ in range(n):
    circles.append(list(map(int, input().split())))

circles.sort()
for i in range(n-1):
    if isMeet(circles[i][0], circles[i][1], circles[i+1][0], circles[i+1][1]):
        print("No")
        sys.exit()

print("Yes")

• 두 원의 위치관계 판별하는 isMeet 함수 구현!
• 원을 입력 받고 원의 중심 x좌표를 기준으로 sort()!
• sort()된 원 리스트에서 연속되는 2개의 원 모두 만나지 않는지 판단할 수 있다면 문제를 풀수 있다고 생각하였다.
• 하지만 실패..
• 원의 중심 x좌표를 기준으로 sort()하고 원의 반지름에 대해서는 고려하지 않았기 때문에 예외케이스가 존재!!
• 해당 문제는 자료구조에 분류된 문제였기 때문에 자료구조를 이용하여 푸는 것을 도전 !!

성공 코드

import sys
input = sys.stdin.readline

n = int(input())
circles = []
stack = []

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

circles.sort()

for i in range(n):
    if circles[i][2] == 0:
        stack.append(circles[i])
    else:
        if stack[-1][2] == 0:
            if stack[-1][1] == circles[i][1]:
                stack.pop()
            else:
                print("NO")
                sys.exit()

print("YES")

풀이

괄호 문제하면 가장 먼저 떠오르는 풀이 방법은 Stack을 이용하는 방법이다. 괄호 문제, 그래프 탐색 외로 Stack을 바로바로 떠올라서 문제를 접근한 적은 드문 것 같다. 해당 문제는 자료구조를 사용하는 문제였기 때문에 최대한 자료구조를 사용하여 문제를 풀어야 겠다고 생각하며 문제에 접근하였다.

고민 끝에 해당 문제는 괄호 문제와 매우 유사하다는 것을 깨달았다.

import sys
input = sys.stdin.readline

백준 문제 풀 때 꿀팁! 백준 문제 중 어떤 문제는 해당 코드를 사용하지 않으면 시간초과를 해결할 수 없는 문제도 있다. 작동 원리는 잘 모르겠지만 습관처럼 백준 문제를 풀 때, 항상 위의 코드를 작성한다. (참고 :input vs sys.stdin.readline)

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

circles.sort()

원의 중심 x좌표와 반지름을 입력받을 때, 각 원이 x축과 만나는 두 개의 좌표를 구했다. 이 때 두 좌표를 크기 순대로 열린괄호, 닫힌괄호라고 생각하면 문제를 풀기 수월할 것이다. 두 좌표를 circles에 따로 따로 저장하기 때문에 둘이 동일한 원의 좌표라는 것을 표시하기 위해 i(인덱스 정보)와 값이 작은 좌표(열린괄호)는 0, 값이 큰 좌표(닫힌괄호)는 1과 함께 저장해주었다.
그리고 x좌표를 기준으로 sort()하였다.

열린괄호 : (           ,           닫힌괄호 : )

for i in range(n):
    if circles[i][2] == 0:
        stack.append(circles[i])
    else:
        if stack[-1][2] == 0:
            if stack[-1][1] == circles[i][1]:
                stack.pop()
            else:
                print("NO")
                sys.exit()

print("YES")

이제는 괄호 문제와 동일하게 풀면된다. 이해하기 쉽게 열린괄호, 닫힌괄호라고 설명하겠다.
circles에 저장된 배열 : [x축과 만나는 좌표, 원을 구별하기 위한 인덱스, 0(첫번째 좌표) / 1(두번째 좌표)]

1. 열린괄호(circles[i][2] == 0) 일 때 stack에 넣어준다.
2. 닫힌괄호(circles[i][2] == 1) 일 때, stack의 마지막에 저장되어 있는 열린괄호(stack[-1][2] == 0)인지 확인하고,
   만약 두 괄호가 짝이라면(tack[-1][1] == circles[i][1]) stack에서 pop()시킨다.
3. 만약 for문 도중 하나라도 짝이 맞지 않으면 "NO"를 프린트하고 프로그램을 종료(sys.exit()) 시킨다.
4. 그게 아니라면, "YES"를 프린트한다.

결과