[Python 3] BOJ - 1689 "겹치는 선분"

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

1689번: 겹치는 선분

 # 풀이 :

 이 문제의 핵심은 정렬과 정보 추가라고 생각한다. 단순히 점을 나열한다면 선분에 대한 정보를 알 수 없다. 만일 (0,2), (1,3)이라는 점 2개가 주어졌다고 하자. 그렇다면 점들의 리스트인 [0,2,1,3]으로는 어떤 선분이 어디에서 겹치는지 알 수 없다. 물론 이중 for문을 사용하면 구할 수는 있지만 N이 백만이기 때문에 시간초과를 피할 수 없다. 따라서 최소 O(NlogN)이나 O(N)인 방법을 생각해야 한다.

 그런데 선분이 겹친다는 것을 생각해보자. 겹치려면 현재 선분을 잇다가 어느 시점에 또 다른 시작점이 생긴 것이다. 따라서 선분의 길이는 크게 중요하지 않다. 오히려 선분이 언제 시작하고 언제 끝나느냐가 더 중요해진다. 그런데 앞서 본 단순 점들의 리스트로는 이 정보를 담을 수 없기 때문에 시작점이면 1, 끝나는 점이면 -1이라는 정보를 추가적으로 담아 준다면 [(0, 1), (2, -1), (1, 1), (3, -1)]의 리스트가 만들어진다.

 그런데 정보를 추가한다고 해도 현재 어느 시점에 어떤 선분이 겹치는지 알기 위해서는 여전히 O(N^2)의 복잡도를 거쳐야 한다. 그런데 선분이 겹치려면 현재 한 선분이 미리 시작했고 끝나지 않았는데 도중에 다른 선분의 시작점이 시작하는 경우이다.

<그림 1>

 현재 그림 1에서 가장 먼저 시작한 선분은 (1,5)선분이다. 따라서 2이상 4이하의 범위에서 시작하는 선분과는 무조건 겹치게 된다. 따라서 (2,5)의 선분과 시점 2에서 만나게 된다. 그런데 문제의 조건에서 선분의 끝에서 만나는 선분은 겹치는 것으로 보지 않는다는 조건이 있다. 따라서 시점 5에서는 원래 가장 먼저 시작한 선분이 끝나게 되므로 겹치는 선분이 없어진다. 또한 (2,5)의 선분도 끝나게 된다. 그런데 (2,5)의 선분이 끝나는 것보다 (5,8)의 선분이 시작하는 것을 먼저 고려한다면 시점 5에서 (1,5), (2,5)와 (5,8)이 겹친다고 판단하게 되므로 문제의 조건을 위반하게 된다.

 따라서 점들의 리스트에 시작점인지 끝점인지에 대한 정보를 추가하고 점들을 오름차순으로 정렬하되, 같은 좌표라면 끝나는 점이 우선적으로 오도록 정렬하게 되면 시간안에 정답을 구할 수 있다. 

 

 # 코드

import sys, functools

# compare : 두개의 튜플을 비교할 때 0번째 원소를 오름차순으로 하되 같으면 1번째 원소를 
#           오름차순으로 정렬하는 함수
def compare(x,y):
    if x[0] < y[0]:
        return -1
    elif x[0] > y[0]:
        return 1
    else:
        if x[1] < y[1]:
            return -1
        elif x[1] > y[1]:
            return 1
        else:
            return 0

# 입력부
n = int(sys.stdin.readline())

# a : 점들을 담는 배열이므로 선분의 갯수가 n이면 점은 2n개 있기 때문에 크기를 2n으로 한다
a = [0] * (2 * n)
# 점 입력
for i in range(n):
    start, end = map(int, sys.stdin.readline().split())
    # 시작점에는 1, 끝점에는 -1을 넣는다
    a[i] = (start, 1)
    a[i + n] = (end, -1)
    
# 정렬
a.sort(key=functools.cmp_to_key(compare))
cnt = 0
ans = []

# 점들을 돌면서 시작하면 만나는 것이므로 +1, 끝나면 겹치지 않으므로 -1을 한 결과를
# 정답배열에 저장한다.
for i in a:
    cnt += i[1]
    ans.append(cnt)
    
# 정답 출력
print(max(ans))