그리디 알고리즘 - 효과적으로 겹치는 구간을 하나로 합치는 방법(스위핑 기본)

1. 문제

 

2170번: 선 긋기 (acmicpc.net)

2170번: 선 긋기

 

2. 풀이

 

x와 y 사이 선을 긋는데, 총 얼마만큼 선을 그었는지 구하는 문제

 

한번 그어진 곳을 또 긋는다고 해서, 중복해서 세지 않는다

 

어려워보여도 예제를 보고 머릿속으로 생각해보면 생각보다 문제가 간단하다

 

4
1 3
2 5
3 5
6 7

 

수직선 위에 1,3을 찍고 그어본다. 그러면 그은 길이가 2인데

 

 

이제 2,5를 찍고 그어본다

 

그러면 총 그은 길이는 4임을 알 수 있는데 어떻게 바로 알 수 있을까?

 

가장 왼쪽의 좌표랑 가장 오른쪽의 좌표를 알면 된다

 

(1,3)과 (2,5)에서 2 <= 3이기 때문에 두 구간이 서로 겹친다.

 

가장 왼쪽의 좌표는 1이고 가장 오른쪽의 좌표는 5이라서, 두 구간을 합치면 (1,5)가 된다.

 

 

다시 3,5를 찍고 그어보면 역시 총 그은 길이는 여전히 4이다.

 

 

그리고 나서 6,7을 찍고 긋는데 이전에 그은 1~5까지와 6~7은 겹치지 않는다

 

그래서 1~5까지 계산한 길이 4에 6~7까지 길이를 새로 구해서 더해줘야한다.

 

그래서 총 길이가 5가 된다

 

 

효율적으로 길이를 구하기 위해 어떻게 해야할지 생각해본다면

 

서로 겹치는 구간의 길이를 구하기 위해서는 가장 왼쪽의 좌표와 가장 오른쪽의 좌표만 알면 된다는 것을 알 수 있다

 

그러면 선분 (x,y)를 가장 왼쪽에서부터 오른쪽으로 순회해야할 것인데

 

그러기 위해 (x,y)를 입력받은 리스트를 x를 기준으로 오름차순으로 정렬하고, x가 같다면 y를 기준으로 오름차순 정렬한다

 

그래서 (1,3), (2,5), (3,5), (6,7) 순으로 순회한다면 위와 같은 상황을 만들 수 있다

 

가장 왼쪽의 좌표와 가장 오른쪽의 좌표는 항상 알고 있어야하고,

 

위 처럼 (1,5)와 (6,7)은 겹치지 않아서 따로 계산해야한다는 것을 알 수 있는데,

 

서로 겹치지 않는 순간 가장 왼쪽의 좌표와 가장 오른쪽의 좌표는 새로 초기화해야할 것이다

 

겹치는 것은 어떻게 알 수 있을까?

 

정렬된 상태에서 첫번째 (x,y)와 두번째 (z,w)가 서로 겹친다면 z <= y이다. 

 

정렬되었기 때문에 z < x일수는 없다

 

그리고 z <= y 조건을 만족한다면, 가장 오른쪽의 좌표가 갱신될 수 있는지 검사해준다. y >= w인지 y <= w인지

 

from sys import stdin

n = int(stdin.readline())

points = []

for i in range(n):
    
    x,y = map(int,stdin.readline().split())

    points.append((x,y))

#왼쪽 좌표를 기준으로 오름차순 정렬
points.sort()

answer = 0

#가장 왼쪽의 좌표와 가장 오른쪽의 좌표를 기억하고
min_x,max_y = points[0]

#정렬된 좌표 리스트를 왼쪽부터 순회하기 시작
for i in range(1,n):
    
    x,y = points[i]
    
    #이미 정렬되었으므로, x < min_x일수는 없다.
    #(min_x,max_y)와 (x,y)가 겹치기 위해서는 (x <= max_y)이다 
    if x <= max_y:
        
        #겹쳤다면, 가장 오른쪽의 좌표를 갱신해준다
        if max_y < y:
            
            max_y = y
    
    #더이상 겹치지 않는다면, 그동안 겹쳐진 구간의 최대 길이를 더해주고,
    else:
        
        answer += (max_y - min_x)
        
        #새롭게 가장 왼쪽의 좌표와 오른쪽의 좌표를 갱신한다
        min_x,max_y = x,y
        
#모든 for문을 수행하면, 마지막 구간의 길이는 더해져있지 않으므로 더해주는것 잊지말기
answer += (max_y - min_x)

print(answer)

 

의외로 문제가 간단해서 놀랍지는 않다...