# 문제
x축 위에 원이 N개 있다. 원은 서로 교차하지 않는다. 하지만, 접할 수는 있다.
원으로 만들어지는 영역이 몇 개인지 구하는 프로그램을 작성하시오.
영역은 점의 집합으로 모든 두 점은 원을 교차하지 않는 연속되는 곡선으로 연결될 수 있어야 한다.
# 입력
첫째 줄에 원의 개수 N(1 ≤ N ≤ 300,000)이 주어진다.
다음 N개 줄에는 각 원의 정보 xi와 ri가 정수로 주어진다. xi는 원의 중심 좌표이며, ri는 반지름이다. (-109 ≤ xi ≤ 109, 1 ≤ ri ≤ 109)
입력으로 주어지는 원은 항상 유일하다.
# 출력
첫째 줄에 원으로 인해서 만들어지는 영역의 개수를 출력한다.
주어진 데이터에서 각 원의 왼쪽 점과 오른쪽 점을 구한다.
왼쪽 점 = 중심 - 반지름
, 오른쪽 점 = 중심 + 반지름
왼쪽 점부터 오름차순으로 정렬해서 원이 완성되는 시점에 영역의 개수를 증가시킨다.
원이 하나 만들어질 때마다 원의 안/밖이 분리되어, 영역이 1 증가한다.
원 안에 원들이 꽉 찰 경우에는, 원의 안/밖 말고도 위 아래도 분리되므로 영역이 2 증가한다.
주어진 데이터에서 각 원의 왼쪽 점과 오른쪽 점을 구한다.
왼쪽 점 = 중심 - 반지름
, 오른쪽 점 = 중심 + 반지름
왼쪽 점인지 오른쪽 점인지의 여부를 L
과 R
로 구분하고 점의 위치
와 함께 저장한다.
for _ in range(n):
x, r = map(int, sys.stdin.readline().split())
# '왼쪽 점인지 오른쪽 점인지 여부'와 '점의 위치'를 저장한다.
circles.append(("L", x - r)) # 왼쪽 점 = 중심 - 반지름
circles.append(("R", x + r)) # 오른쪽 점 = 중심 + 반지름
정렬의 기준
1순위) 점의 위치를 오름차순으로 정렬한다.
2순위) 점의 위치가 같을 경우, 오른쪽 점 R
이 왼쪽 점 L
보다 앞으로 오도록 정렬한다.
원 두 개가 맞닿아 있는 경우에는, 왼쪽 점과 오른쪽 점의 위치가 동일하다.
이때 왼쪽에 있는 원을 먼저 완성시키고 오른쪽 원을 계산해야 하므로,
오른쪽 점 R
이 먼저 오도록 정렬하는 것이다.
# 오른쪽 점 R이 왼쪽 점 L보다 앞으로 오도록 정렬
circles.sort(key=lambda x: (x[0]), reverse=True)
# 왼쪽 점부터 오름차순으로 정렬
circles.sort(key=lambda x: x[1])
왼쪽 점은 원의 시작을 의미한다.
이후 반복을 돌면서 오른쪽 점을 만나면 원이 완성된다.
이후에 만날 오른쪽 점을 위하여 stack
에 담아둔다..
stack = [] # 왼쪽 점과 완성된 원의 정보를 담을 스택
count = 1 # 영역 개수
for circle in circles:
# 현재 점이 왼쪽 점인 경우들만, stack에 담아둔다.
if circle[0] == "L":
stack.append(circle)
continue
circles를 돌면서 나오는 circle[0]이 L
이 아닌 경우는 (else)
circle[0]이 R
을 의미하며, 이때 가장 최근에 만난 L
로 시작한 원이 완성된다.
(circle에는 L 혹은 R만 넣어놨으니, L이 아니면 R이다,, 당연하쥐...)
stack에 값이 있다는 것은, 현재 원이 시작되고 나서 아직 원이 닫히지 않았음을 의미한다.
그러므로 stack의 요소가 있으면 실행하도록 while문 작성!
스택에 가장 최근에 쌓인 것을 꺼내서 이전 요소를 의미하는 prev
에 담아 둔다.
# 현재 점이 '오른쪽 점'인 경우에만 아래 코드 수행
while stack:
# 스택에 가장 최근에 쌓인 것 꺼냄
prev = stack.pop()
가장 최근에 만난 L
을 스택에서 꺼낸다면 원이 완성된다.
(스택에 가장 최근에 쌓인 값이 L
이 아닐 수도 있다..! 그건 아래에서 나옴 😄)
L
을 꺼냈다면 원이 완성되었다!
원의 너비를 계산한다. (아래에서 필요함)
너비 = 현재 점(오른쪽 점) - 이전 점(왼쪽 점)
# L을 꺼낸 경우 == 스택에서 꺼낸 게 왼쪽 점인 경우 -> 원이 만들어짐
if prev[0] == "L":
# 너비 = 현재 점(오른쪽 점) - 이전 점(왼쪽 점)
width = circle[1] - prev[1]
원이 만들어져서 원의 안/밖으로 영역이 증가했으므로, count를 1 증가한다.
원이 만들어지면 stack에 원을 의미하는 C
와 위에서 계산한 원의 너비를 추가한다.
count += 1
# 원이 만들어졌으므로 stack에 원을 의미하는 C와 너비 추가
stack.append(("C", width))
# 원이 닫히면 다음으로 넘어간다.
break
stack에서 원을 꺼낸 경우, 현재 원 안에 원이 또 존재하는 것을 의미한다.
현재 원 안에 있는 원이 여러개인 경우에는, 이 원들이 현재 원을 가득 채우고 있는지 확인해야 한다.
(이 확인은 아래 6단계에서 할 거임!)
현재 원을 가득 채우고 있는지 검증할 때 사용하기 위해 원을 꺼낼 때마다
total_width
에 꺼낸 원의 width를 추가한다.
# C를 꺼낸 경우 == 스택에서 꺼낸 게 원인 경우 -> 현재 원 안에 존재하는 원을 의미
elif prev[0] == "C":
total_width += prev[1]
현재 원 안에 존재하는 원들의 너비는 total_width
에 전부 추가해두었다.
(stack에서 C
를 꺼낼 때마다 추가해놨음)
현재 원이 닫힐 때, 현재 원의 너비가 안에 존재하는 원들의 너비 총합과 동일하다면
작은 원들이 가득 채우고 있는 것이다.
현재 원을 가득 채우고 있는 경우에는 원이 위/아래로 분리되므로 count를 2 증가한다.
# 현재 만들어진 원의 지름이 이전의 원들 지름의 합과 같을 경우
# 현재 원을 꽉 채우고 있으므로 count를 2 증가
if total_width == width:
count += 2
# L을 꺼낸 경우 == 가장 최근에 스택에 쌓인 게 왼쪽 점인 경우 -> 원이 만들어짐
if prev[0] == "L":
# 너비 = 현재 점(오른쪽 점) - 이전 점(왼쪽 점)
width = circle[1] - prev[1]
# 현재 만들어진 원의 지름이 이전의 원들 지름의 합과 같을 경우
# 현재 원을 꽉 채우고 있으므로 count를 2 증가
if total_width == width:
count += 2
# 다를 경우, count 1 증가
else:
count += 1
# 원이 만들어졌으므로 stack에 원을 의미하는 C와 너비 추가
stack.append(("C", width))
# 원이 닫히면 다음으로 넘어간다.
# 지금 원을 추가했기 때문에 stack에 값이 있어서 break를 안해주면 탈출하지 못한다!!
break
# C를 꺼낸 경우 == 가장 최근에 스택에 쌓인 게 원인 경우 -> 현재 원 안에 존재하는 원을 의미
elif prev[0] == "C":
total_width += prev[1]
끝~!
전체 코드
import sys
n = int(input())
circles = []
for _ in range(n):
x, r = map(int, sys.stdin.readline().split())
# '왼쪽 점인지 오른쪽 점인지 여부'와 '점의 위치'를 저장한다.
circles.append(("L", x - r)) # 왼쪽 점 = 중심 - 반지름
circles.append(("R", x + r)) # 오른쪽 점 = 중심 + 반지름
# 오른쪽 점 R이 왼쪽 점 L보다 앞으로 오도록 정렬 (왼쪽 점과 오른쪽 점이 만나는 경우, 닫히는 점인 오른쪽이 먼저 있어야 함)
circles.sort(key=lambda x: (x[0]), reverse=True)
# 왼쪽 점부터 오름차순으로 정렬
circles.sort(key=lambda x: x[1])
stack = [] # 왼쪽 점과 완성된 원의 정보를 담을 스택
count = 1 # 영역 개수
for circle in circles:
# 현재 점이 왼쪽 점인 경우들만, stack에 담아둔다.
if circle[0] == "L":
stack.append(circle)
continue
# 현재 점이 '오른쪽 점'인 경우에만 아래 코드 수행
# 현재 열린 원 안에 원이 들어있을 경우, 그 원들의 너비를 전부 더해서 담을 변수
# -> 이게 현재 원의 크기와 같으면 현재 원을 꽉 채우고 있으므로 count를 2 증가시켜줄 예정
total_width = 0
while stack:
# 스택에 가장 최근에 쌓인 것 꺼냄
prev = stack.pop()
# L을 꺼낸 경우 == 스택에서 꺼낸 게 왼쪽 점인 경우 -> 원이 만들어짐
if prev[0] == "L":
# 너비 = 현재 점(오른쪽 점) - 이전 점(왼쪽 점)
width = circle[1] - prev[1]
# 현재 만들어진 원의 지름이 이전의 원들 지름의 합과 같을 경우
# 현재 원을 꽉 채우고 있으므로 count를 2 증가
if total_width == width:
count += 2
# 다를 경우, count 1 증가
else:
count += 1
# 원이 만들어졌으므로 stack에 원을 의미하는 C와 너비 추가
stack.append(("C", width))
# 원이 닫히면 다음으로 넘어간다.
# 지금 원을 추가했기 때문에 stack에 값이 있어서 break를 안해주면 탈출하지 못한다!!
break
# C를 꺼낸 경우 == 스택에서 꺼낸 게 원인 경우 -> 현재 원 안에 존재하는 원을 의미
elif prev[0] == "C":
total_width += prev[1]
print(count)