백준 1689 겹치는 선분 파이썬

1차원 좌표계 위에 선분 N개가 있다. 선분이 최대로 겹쳐있는 부분의 겹친 선분의 개수를 구해보자. 선분의 끝 점에서 겹치는 것은 겹치는 것으로 세지 않는다.

 

예제 입력	예제 출력
11 1 2 3 6 7 8 10 11 13 16 0 5 5 6 2 5 6 10 9 14 12 15	3

 

문제 바로가기

---

백준의 철로 문제와 비슷한 유형이라고 생각됩니다. 골드 2의 문제이니 먼저 풀고 오시는 것을 추천합니다.

 

문제 해석

서로 겹치는 선분의 최대 개수가 아니라, 겹쳐 있는 부분의 최대 개수를 구하는 문제였습니다. 처음에 문제를 읽고 전자로 오해해서 시간이 좀 걸렸지만 문제를 다시 읽어본 후 후자라는 것을 알아차렸습니다. 처음 문제를 읽을 때 꼼꼼히 잘 읽어봐야겠습니다.

 

라인 스와핑

철로 문제를 풀어봤기 때문에 푸는 방법은 바로 떠올랐습니다. 라인 스와핑 방식으로 선을 일정 기준으로 정렬한 후 방향을 정해 하나씩 봐나가는 방법입니다.

 

또한 최대 개수만 구하면 됨으로, 범위를 따로 구해서 비교한다던가하는 과정은 필요없었습니다. 라인 시작점을 1로, 라인 끝 점을 -1로 두고 좌표를 오름차순으로 정렬해 최대 개수를 구했습니다.

 

전체 코드

import sys
input = sys.stdin.readline

# 선분의 개수
n = int(input())

lines = []
for _ in range(n):
    a, b = map(int, input().split())
    lines.append([a, 1])
    lines.append([b, -1])

lines.sort()

maxcount = 0
count = 0

for _, value in lines:
    count += value
    maxcount = max(maxcount, count)

print(maxcount)