[백준/2170] 선 긋기 (Python)

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

2170번: 선 긋기

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:09:22

 

---

 

문제 설명

 

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

 

입력 및 출력

 

입력

첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

 

출력

첫째 줄에 그은 선의 총 길이를 출력한다.

 

입력 예시

4
1 3
2 5
3 5
6 7

 

출력 예시

5

 

 

---

 

풀이

 

라인스위핑 문제. 이쯤되면 슬슬 요 타입도 공식화되는 것 같다.

 

핵심은 '단 한번의 순회를 통해' '모든 겹칠 수 있는 선들을 묶는 것'이라고 볼 수 있다. 그러기 위해서는 우선 다음과 같은 과정이 필요하다.

 

• 정렬 : 시작점을 기준으로 정렬함으로써, 나중의 시작점은 이전의 시작점보다 좌표가 같거나 큰 상태를 유지한다.
• 순회 : 이전 선분의 시작점 prev_x와 끝점 prev_y을 저장한 상태에서, 다음 선의 시작점 x, 끝점 y를 입력받았다고 가정하자.
  • x <= prev_y : 이 경우, 이전 선분의 시작점과 끝점 사이에 현재 선분이 존재함을 의미한다. 따라서 이전 선분과 현재 선분을 합친 새로운 선분을 만들어낼 수 있다. 이 때 이 선분의 좌표는 (prev_x, max(y, prev_y))가 된다.
  • x > prev_y : 이 경우, 이전 선분과의 접점이 존재하지 않으므로 새로운 선분을 만들어야 한다. 이전 선분의 길이를 저장하고, 새로운 선분 (x, y)으로 교체하여 다음 순회로 이어간다.

이런 식으로 진행하면 정렬 알고리즘의 시간복잡도 이내로 순회가 가능하다!

 

 

풀이 코드

import sys
input = sys.stdin.readline

N = int(input())
n_list = [list(map(int, input().split())) for _ in range(N)]
n_list.sort(key = lambda x : (x[0], -x[1]))

result = 0

prev_x, prev_y = n_list[0]
for x, y in n_list[1:] :
  if prev_y < x :
    result += prev_y - prev_x
    prev_x, prev_y = x, y
  elif prev_y < y :
    prev_y = y

print(result + prev_y - prev_x)

풀이 완료!