[백준-파이썬] 23740: 버스 노선 개편하기

문제로 가기

정렬하고 쭉 ~ 한번 보면 되는 스위핑 문제!!

정렬한 후에 (출발지가 앞쪽인 순서, 출발지가 같으면 도착지가 앞쪽일 수록 앞에)
쭉~ 보면서 두 노선씩 비교한다.

a_route는 처음 노선으로 초기화하고 시작하고, b_route는 그 다음 노선부터 끝까지 쭉 본다.
만약 a, b 노선이 겹친다면 합쳐서 새로운 노선으로 만든다! 이때 요금은 더 낮은 쪽을 따른다.

출발점이 더 나중에어도, 도착점이 더 이른 노선이 있을 수도 있다. 노란 색 노선, 빨간 색 노선을 비교할 때는.. 일단 겹치니까 a_route를 업데이트하는데, 'a_route = (a_route[0], max(a_route[1], b_route[1]), min(a_route[2], b_route[2]))'에서 'max(a_route[1], b_route[1])' 이렇게 해야 한다!
처음 풀 때는 그냥 'b_route[1]'로 해서 틀렸다.!

겹치지 않으면, 그때까지 합친 노선(a_route)을 새로운 result_route에 추가한다.
그리고 a_route를 이제부터 볼 새로운 노선으로 업데이트 한다.

for문 끝까지 돈 후에, 반영 안된 노선이 있을 수 있으니 반영해준다.

그리고 출력하면 끝!!

import sys

input = sys.stdin.readline

MIIS = lambda: map(int, input().split())

N = int(input())

bus_route = []

for _ in range(N):
    S, E, C = MIIS()
    bus_route.append((S, E, C))

# 정렬
bus_route.sort()

result_route = []

a_route = bus_route[0]  # 처음 노선
for i in range(1, N):
    # 두 노선을 보면서
    b_route = bus_route[i]

    # 겹치면 합쳐서 새로운 노선으로 만들기
    if a_route[1] >= b_route[0]:
        a_route = (a_route[0], max(a_route[1], b_route[1]), min(a_route[2], b_route[2]))

    else:  # 안 겹치면 그때까지 합친 노선을 새롭게 result_route에 추가하고, 새로운 노선 만들기
        result_route.append(a_route)
        a_route = bus_route[i]

# 반영 안한 노선 있으면 반영
if a_route not in result_route:
    result_route.append(a_route)

print(len(result_route))
for route in result_route:
    print(*route)