[백준/BOJ] gold5 - 23740번 버스 노선 개편하기 (Python)

▶23740 - 버스 노선 개편하기

▶문제

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

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

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

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

 

▶입력

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

두 번째 줄부터 N개의 줄에 각 버스 노선을 나타내는 세 정수 S, E, C가 주어진다.

(0 ≤ S < E ≤ 10^9, 1 ≤ C ≤ 10^9)

 

▶출력

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

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

 

▶풀이

제일 먼저 받아온 노선을 정렬해, 출발 값이 빠른 노선부터 확인하면 된다.

result에 노선에 맞게 하나씩 넣어준다.

만약에 다시 들어오는 노선의 출발 값이 이미 들어있는 노선의 출발, 도착 값 사이에 있다면 업데이트해준다.

도착 값은 더 큰 값으로, 가격은 더 작은 값으로 수정해준다.

 

그리고 출발, 도착 값 사이에 있지 않다면, 새로운 노선을 추가해주고 이후부터는 그 값과 비교해준다.

이 과정을 반복한다.

n = int(input())
tmp = []
for _ in range(n):
    s, e, c = map(int, input().split())
    tmp.append([s, e, c])

tmp.sort()
result = []
check = 0
for i in range(len(tmp)):
    if i == 0:
        result.append(tmp[i])
    else:
        if result[check][0] <= tmp[i][0] <= result[check][1]:
            result[check][1] = max(result[check][1], tmp[i][1])
            result[check][2] = min(result[check][2], tmp[i][2])
        else:
            result.append(tmp[i])
            check += 1
print(len(result))
for res in result:
    for r in res:
        print(r, end=' ')
    print()