[백준]2170 선긋기 #라인스위핑

1. 풀이

visited로 선이 그어진곳을 표시하기엔 범위가 -1,000,000,000 이상 1,000,000,000 이하 이므로 메모리초과.

N의 범위가 N(1≤N≤1,000,000) 이므로 무조건 O(N)으로 풀어야된다. 풀이는 아래와 같다.

(1) 선을 sort()해준다. 그럼 시작점 순서대로 소팅된다.

(2) preA<=nowA 이므로 아래와 같은 경우의 수만 나올 수 있다.

(i-1번째 선분 : 빨간선분, 시작점은 preA, 끝점은 preB 이고,

i번쨰 선분 : 파란선분, 시작점은 nowA, 끝점은 nowB 일때)

​

i) preB<nowA : 안겹치는경우

preAㅡㅡㅡㅡㅡpreB

                      nowAㅡㅡㅡㅡㅡㅡnowB

ii) nowA<=preB<nowB

preAㅡㅡㅡㅡㅡpreB

            nowAㅡㅡㅡㅡㅡㅡㅡㅡnowB

iii) preB<nowB

preAㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡpreB

          nowAㅡㅡㅡㅡㅡnowB

​

(3) 누적된 상태에서 확인이 되므로 N번만 반복하면 된다는것이 핵심.

​

2. 소스코드

import sys
N=int(input())
L=[]
for i in range(N):
    a,b=map(int,sys.stdin.readline().rstrip().split())
    L.append([a,b])

L.sort()
preA,preB=L[0][0],L[0][1]
ans=preB-preA
for i in range(1,N):
    nowA,nowB=L[i][0],L[i][1]
    #겹치지 않는경우
    if preB<nowA:
        ans+=nowB-nowA
        preA, preB = nowA, nowB
    #살짝겹치는경우
    elif nowA<=preB<nowB:
        ans+=(nowB-preB)
        preA, preB = nowA, nowB



print(ans)