[Baekjoon Online Judge] 백준 2170번 선 긋기(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2170번 선 긋기

(Python)

(글쓴날 : 2020.05.17)

 

---

* Baekjoon Online Judge, 백준 2170번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2170번 선 긋기

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/2170

2170번: 선 긋기

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

도화지에 자를 대고 N번 선을 그을 때, 주어진 두 점들을 참고해서 그은 선의 전체 길이를 구하는 문제입니다.

단, 선이 여러 번 그려진 곳은 한 번씩만 계산합니다.

 

저의 경우, 라인 스위핑을 적용하였고, Python을 사용했습니다.

먼저, 시작점과 끝점을 튜플 형태로 리스트화하여 저장한 후, 시작점을 기준으로 오름차순 정렬하였습니다.

그 후, 차례대로 선의 길이를 더해가며 만약, 현재 시작점과 끝점이 이전 시작점과 끝점에 포함되거나 겹치는 경우를 조건문으로 분기해 중복된 선의 길이를 제거하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
N = int(input())
lines = []
 
for _ in range(N):
    s, n = map(int, input().split())
    lines.append((s, n))
 
lines.sort()
ans = 0
bS = bE = 0
 
for s, e in lines:
    if not ans:
        ans = abs(e - s)
        bS = s
        bE = e
        continue
 
    if bS <= s and bE >= e:
        continue
    
    ans += abs(e - s)
 
    if bE > s:
        ans -= abs(bE - s)
    
    bS = s
    bE = e
 
print(ans)

---