[Python/BOJ] 23740. 버스 노선 개편하기

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

23740번: 버스 노선 개편하기

문제

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

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

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

입력

첫 번째 줄에 버스 노선의 수 N이 주어진다. (1≤N≤200000)

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

출력

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

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

풀이

Code

import sys
input = sys.stdin.readline

def solution(n, information) :
    # 1. 출력 리스트 생성
    ans = []
    # 2. 버스 노선 정보 정렬
    information.sort()
    # 3. 초기 s, e 세팅
    s, e, c = information[0]
    # 4.
    for i in range(1, n) :
        ns, ne, nc = information[i]
        # 4-1. 현재 도착 노선과 해당 인덱스의 출발점이 연결되지 않았을 경우
        if e < ns :
            # 출력 리스트에 정보 입력
            ans.append([s, e, c])
            # s, e 재정의
            s, e, c = ns, ne, nc
        # 4-2. 현재 도착 노선이 해당 인덱스의 출발점을 포함하는 경우
        else :
            # e, 비용 재설정
            e, c = max(e, ne), min(c, nc)
    # 5. 마지막 노선 정보 삽입
    ans.append([s, e, c])
    # 6. 결과 출력
    print(len(ans))
    for line in ans :
        print(*line)

if __name__ == '__main__' :
    n = int(input())
    information = [list(map(int, input().split())) for _ in range(n)]
    solution(n, information)