[BOJ] (G2) 1689. 겹치는 선분

👨‍💻 개인 공부 기록용 블로그 입니다.
💡 틀린 내용이나 오타는 댓글, 메일로 제보해주시면 감사하겠습니다!! (__)

링크

https://www.acmicpc.net/problem/1689

문제

문제 설명 및 요점

• 선분 100만개가 시작 좌표와 끝 좌표로 주어진다.
• 선분의 좌표는 절댓값이 10억보다 같거나 작은 정수이다.
• 선분 끝 점에서 겹치는 것은 세지 않는다. 최대로 겹쳐있는 부분의 겹친 선분 개수를 구한다.

풀이

#스위핑 #그리디 #정렬

• 처음부터 끝까지 단 한 번만 탐색해서 구하는 기법인 스위핑을 사용한다.
• 스위핑을 위해서, 입력받는 선분을 파싱하여 저장한다.
  • 시작점은 +1 을 붙여서, 끝점은 -1을 붙여서 저장한다. [[스위핑- +1 -1 테크닉]]
  • 저장한 점들을 정렬한다.
• 정렬된 점들을 하나씩 읽어가면서, +1 또는 -1을 가지고 누적합을 계산한다.
• 누적합이 바로 겹쳐있는 선분의 개수이다.
• 점을 하나씩 볼 때마다 정답을 갱신해주면 된다.

코드

import sys
input = sys.stdin.readline

n = int(input())
points = []
for _ in range(n):
    s, e = map(int, input().split())
    points.append((s, 1))
    points.append((e, -1))
points.sort()

pSum = 0
answer = 0
for x, v in points:
    pSum += v
    answer = max(answer, pSum)
print(answer)