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

내가 짠 코드

...

• 풀지 못하였다.
• 2504 - 괄호의 값과 유사하게 원의 시작점과 끝점을 나누면 될 것이라 생각하였지만,
  • 원의 시작 요소와 끝 요소를 배열에 담아도 해당 원이 끝났다는 것을 어떻게 판단할지 아이디어가 없었다.
  • 같은 점에 여러 원의 요소가 있을 경우 큰 원의 요소가 바깥에 가고, 작은 원의 요소를 안에 가도록 정렬해야 하는데 그 방법이 떠오르지 않았다.
  • 작은 원으로 큰 원의 지름이 꽉 찰 경우 영역이 2개 생기고, 아닌 경우 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)

• 처음에 입력 받은 값을 이용하여 2개의 튜플을 만든다.

  • 첫 번째 정보는 왼쪽 끝인지 오른쪽 끝인지에 관한 정보다.
  • 두 번째는 해당 끝의 좌표이다.

• 튜플들을 정렬한다.

  • 첫 번째 요소를 경우 R이 L보다 앞에 오도록 정렬한다. (내림차순으로)

    • 이후 정렬을 한번 더 할 것인데, 같은 좌표에 있는 경우 닫히는 경우가 열리는 경우보다 우선하여 일어나게 하기 위함이다.

  • 두 번째 요소를 오름차순 정렬한다.

    • 이때 값이 같을 경우 앞에서 한 정렬의 순서가 보장된다.

    정렬이 보장되는 것에 대한 GPT의 답

• 튜플들의 리스트를 하나씩 순회한다.

  • L 인 경우
    • 원의 시작이다.
    • 스택에 push 한다.
  • R인 경우
    • total_width를 0으로 초기화한다.
    • stack에서 요소 하나를 pop한다. → 이전 요소를 확인한다.
      • 이전 요소가 L (원의 시작) 인 경우
        • 원을 만든다.
        • 원의 너비는 현재 요소 R의 좌표와 이전 요소 L의 좌표의 차이다.
        • 원의 너비를, 이전에 나온 C(원 안의 원)들로 인해 만들어진 total_width와 비교한다.
          • 만약 같다면 원 안에 있는 원들로 인해 큰 원이 양분 된단 이야기다 → 공간이 2개 생긴다.
          • 만약 다르다면 양분되지 않는단 이야기다 → 공간이 1개 생긴다.
        • 스택에 새로 만들어진 원을 push한다.
      • 이전 요소가 C (원 안의 원) 인 경우
        • 너비를 total_width에 더해준다 → 원 안의 원들의 너비의 합을 위에서 사용한다.

• 원들로 만들어진 공간의 개수를 구했으니 출력해준다.

참고

https://e-juhee.tistory.com/entry/python-백준-10000-원-영역-스택