[백준/Python] 2170 - 선 긋기

import sys
input = sys.stdin.readline


spots = []
for _ in range(int(input())):
  s, e = map(int, input().split())
  spots.append((s,e))

spots.sort(key= lambda x: x[0])

stack = []
for s, e in spots:
  if not stack or stack[-1] < s:
    stack.append(s)
    stack.append(e)
  else:
    if stack[-1] < e:
      stack.pop()
      stack.append(e)

result = 0
for i in range(0, len(stack)-1, 2):
  s, e = stack[i], stack[i+1]
  result += abs(e-s)
print(result)

Hint

선의 길이를 재는 것이므로 시작점과 끝점만 알면 된다.

음수가 범위에 포함되어 있으니 이를 고려하는 걸 잊지 말자!!

 

풀이 과정

스택에는 시작점과 끝점을 기록한다. (A, B) (C, D) 이렇게 쌓음 -> 스택으로는 [A, B, C, D] 이렇게 쌓일 것이다.

스택이 비어있거나, top이 s 보다 작으면 이어지는 관계가 아니라 끊어진 선 관계이므로 stack에 (시작점, 끝점)을 추가한다.

top이 s보다 크면 이어진 선이 된다! -> e가 top보다 작으면 포함관계이므로 현재 stack을 유지하고, e가 더 크다면 더 길게 선을 그을 수 있게 되므로 top을 빼고 e를 새로운 끝점으로 넣는다

 

그리고 쌍 관계로 꺼내서 길이를 계산하면 된다.