23740(버스 노선 개편하기) - 해결

버스 노선 개편하기

 

문제

서강 나라에서는 일직선 도로를 따라 $N$개의 버스 노선을 운영 중이다. 필요할 때마다 노선을 새로 만든 탓에 겹치거나 중복되는 노선이 많다. 복잡한 버스 노선에 지친 시민들을 위해 버스 노선을 개편하기로 했다.

각 버스 노선은 세 정수 $S$, $E$, $C$로 나타낼 수 있으며, 구간 $[S,E]$를 요금 $C$로 운행한다는 뜻이다. 어떤 두 버스 노선의 구간이 한 점 이상에서 겹친다면, 두 구간을 합친 새 노선으로 대체한다. 이때 요금은 더 낮은 금액의 요금을 따르기로 했다. 버스 노선 개편은 구간이 겹치는 버스 노선이 없을 때까지 진행한다.

그림 D.1: 개편 전과 개편 후의 버스 노선도

버스 노선들의 정보가 주어지면, 개편이 끝난 후 버스 노선의 정보를 출력하는 프로그램을 작성하자.

 

입력

첫 번째 줄에 버스 노선의 수 $N$이 주어진다. ($1 \le N \le 200\,000$)

두 번째 줄부터 $N$개의 줄에 각 버스 노선을 나타내는 세 정수 $S$, $E$, $C$가 주어진다. ($0 \le S \lt E \le 10^9$, $1 \le C \le 10^9$)

 

출력

첫 번째 줄에 개편이 끝난 후의 버스 노선의 수 $K$를 출력한다.

두 번째 줄부터 $K$개의 줄에 개편 후 각 버스 노선의 $S$, $E$, $C$를 $S$가 작은 순서대로 출력한다.

---

스위핑문제의 핵심은 정렬과 어떻게 연결할지가 관건이다.

그래서 정렬은 처음 시작 S를 기준으로 하였다. 그 이유는 출력 자체를 S가 작은 순으로 하기도하고 

앞의 E가 뒤의 S 보다 작다면 이어질 수 없다는 성질을 이용하기 위해서 이렇게 적용하였다.

그리고 C같은 경우는 이어주면서 크기를 비교해서 작은 걸 선택하였다.

빈 리스트를 만들어서 담는 방식으로 버스노선을 저장하였다.

하지만 처음에는 맞다고 생각하였는데 계속 틀렸다.

그 이유는 연결하는 방싱이 문제였다. 무조건 앞의 E가 뒤의 E보다 작다고 생각하여 틀렸다.

그 부분을 수정하니 정답이였다.

import sys
input = sys.stdin.readline

N = int(input())

# 버스 노선 저장
bf_bus_list = []
for _ in range(N):
    bf_bus_list.append(list(map(int,input().split())))
# S를 기준으로 정렬
bf_bus_list.sort()

# 개편된 노선을 저장하기위한 리스트
# 처음 노선을 미리 저장
af_bus_list = [bf_bus_list[0][:]]

# 다음 노선부터 파악
for i in range(1,N):
    S, E, C = bf_bus_list[i][:]
    # 개편된 노선의 가장 마지막 노선의 E가 S보다 작다면 끊어진 것
    # 그렇기 때문에 새로운 노선을 만든다.
    if af_bus_list[-1][1] < S:
        af_bus_list.append([S,E,C])
    # 그렇지 않다면 이전의 노선과 이어질 수 있다.
    else:
        # 개편된 노선의 E는 더 긴 쪽을 택한다.
        if af_bus_list[-1][1] < E:
            af_bus_list[-1][1] = E
        # 개편된 노선의 C는 더 작은 쪽을 택한다.
        if af_bus_list[-1][2] > C:
            af_bus_list[-1][2] = C
# 길이 축력
print(len(af_bus_list))
# 노선 출력
for _list in af_bus_list:
    print(*_list)