[백준/Python] 2170 - 선 긋기

2023. 9. 2. 01:56· Algorithm/BaekJoon
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를 새로운 끝점으로 넣는다

 

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

'Algorithm > BaekJoon' 카테고리의 다른 글

[백준/Python] 2146번 - 다리 만들기  (0) 2023.09.06
[백준/Python] 2573번 - 빙산  (0) 2023.09.06
[백준/Python] 1874번 - 스택 수열  (0) 2023.09.02
[백준/Python] 2493번 - 탑  (0) 2023.09.01
[백준/Python] 10828번 - 스택  (0) 2023.09.01
'Algorithm/BaekJoon' 카테고리의 다른 글
  • [백준/Python] 2146번 - 다리 만들기
  • [백준/Python] 2573번 - 빙산
  • [백준/Python] 1874번 - 스택 수열
  • [백준/Python] 2493번 - 탑
빵빵0
빵빵0
(아직은) 공부하고 정리하는 블로그입니다.
빵빵0
Hack Your World
빵빵0
전체
오늘
어제
  • 분류 전체보기 (79)
    • Error Handling (7)
    • Project (5)
    • Computer Science (4)
      • Data Structure (2)
      • Database (1)
      • Cloud (0)
      • OS (0)
      • Infra, Network (1)
      • AI (0)
    • Language (4)
      • Go (3)
      • Rust (1)
      • Python (0)
      • Java (0)
    • Algorithm (39)
      • BaekJoon (18)
      • Programmers (7)
      • LeetCode (6)
      • NeetCode (8)
    • SW Books (9)
      • gRPC Up & Running (1)
      • System Design Interview (2)
      • 스프링 입문을 위한 자바 객체지향의 원리와 이해 (6)
      • 블록체인 해설서 (0)
      • 후니의 쉽게 쓴 CISCO 네트워킹 (0)
    • Own (3)
      • Personal (1)
      • Novel (0)
      • Memo (2)
    • BlockChain (4)
      • Issues (0)
      • Research (4)
      • Tech (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Palindrome
  • Programmers
  • 프로그래머스
  • MongoDB
  • Hash Table
  • BaekJoon
  • Python
  • chart
  • golang
  • decimal
  • KBW
  • LeetCode
  • 그리디
  • 스택
  • 블록체인
  • NeetCode
  • 큐
  • BFS
  • go
  • 2024
  • two pointer
  • BEAKJOON
  • Event
  • 백준
  • DP
  • candlechart
  • 해시
  • blockchain
  • Greedy
  • ohlcv

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
빵빵0
[백준/Python] 2170 - 선 긋기
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.