[백준][구현] 2170. 선긋기

2170. 선긋기

2170번: 선 긋기

기본 선긋기 문제 - 외워두는게 좋을 것같음

 

 

• 첫 시도
  
  • 입력값이 매우 크기 때문에 완탐 절대 불가
  • 값이 들어오면 현재 end값과 입력된 start값 크기 비교해서 길이 계산
    • -> 입력값이 앞순서부터가 아닐 수 있어서 틀림
    • -> 입력값에 음수가 들어갈 수 있어서 시작값을 0으로 설정해서 틀림

import sys
input = sys.stdin.readline

n = int(input())
cur_start, cur_end = 0, 0
result = 0

for i in range(n):
    s, e = map(int, input().split())
    if cur_end < s:
        result += (cur_end-cur_start)
        cur_start = s
    cur_end = max(cur_end, e)

# 마지막 길이 더해주기
result += cur_end-cur_start
print(result)

 

 

• 재시도
  • 정렬
    • 하나씩 입력받으면서 체크할 수 없고 모두 입력받은 후 정렬 해줘야함
  • 음수처리
    • 시작값은 -INF로 해준다

n = int(input())
cur_start, cur_end = -int(1e9), -int(1e9)
result = 0

lst = []
for i in range(n):
    s, e = map(int, input().split())
    lst.append((s, e))

lst.sort()
for s, e in lst:
    if cur_end < s:
        result += (cur_end-cur_start)
        cur_start = s
    cur_end = max(cur_end, e)

# 마지막 길이 더해주기
result += cur_end-cur_start
print(result)