[백준 2170번] 선 긋기 - Python

 

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

2170번: 선 긋기

풀이

사용한 알고리즘 : 라인 스위핑

 

※ 풀이 전략

1. 입력 받은 선들을 시작점 기준으로 오름차순 정렬한다.

2. 맨 처음 입력한 선분의 시작점을 start, 끝점을 end로 둔다.

3. 다음 선의 시작점이 end보다 작으면 end는 해당 선의 끝점으로,

    다음 선의 시작점이 end보다 크면 start는 해당 선의 시작점, end는 해당 선의 끝점으로 변경한다.

4. 위 3번 과정에서 start가 변할 때마다 변경하기 전의 end-start 값을 총 합계에 합산한다.

5. 3~4번 과정을 반복한다.

6. 마지막 선분의 연산을 위해 기존 sum에 end-start를 더해준다.

7. 합계 출력

 

아래 그림은 문제에서 준 예제 입력을 순서대로 도식화한 것이다.

import sys

input=sys.stdin.readline

n=int(input())

line=[]
for i in range(n):
    a,b=map(int,input().split())
    line.append((a,b))

line.sort()

start=line[0][0]
end=line[0][1]
sum=0

for i in line:
    if end<i[0]:
        sum+=end-start
        start=i[0]
        end=i[1]
    else:
        if end<i[1]:
            end=i[1]
sum+=end-start

print(sum)