[Python] 23740번 버스 노선 개편하기

 

 

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

23740번: 버스 노선 개편하기

---

 

23/09/02

 

 

스위핑 기초를 다질 수 있는 문제로, 2170번 선 긋기 문제의 응용 버전 문제라고 생각할 수 있다.

 

---

 

문제 접근 방식:

 

 

문제 접근 방식은 다음과 같다.

 

 

1. $N$개의 입력 $S, E, C$를 $S$를 중심으로 내림차순 정렬한다.

 

2. 이후 리스트에서 마지막 원소(시작 지점이 가장 작은 버스)를 뽑아 새로 만드는 버스 노선의 시작 지점, 도착 지점, 비용($\textrm{now_S, now_E, now_C}$)을 저장한다.

 

3. 이후 리스트가 빌 때까지 다음과 같은 행동을 반복한다.

 

- 리스트의 마지막 원소를 뽑는다. 이를 $\textrm{S, E, C}$라고 하자.

 

- 새로 만드는 버스 노선의 도착 지점보다 방금 뽑은 버스 노선의 시작 지점이 더 작거나 같다면, 즉, $\textrm{S} \leq \textrm{now_E}$라면, 우리는 방금 뽑은 버스 노선을 새로 만드는 버스 노선에 겹칠 수 있다.

 

- 이후 겹치는 작업을 시행해준다. 이 과정에서 방금 뽑은 버스 노선의 비용이 더 작다면 새로 만드는 버스 노선의 비용을 갱신해 준다.

 

- 만약 새로 만드는 버스 노선의 도착 지점보다 방금 뽑은 버스 노선의 시작 지점이 더 크다면, 즉, $textrm{S} > \textrm{now_E}$라면, 우리는 방금 뽑은 버스 노선을 새로 만드는 버스 노선에 겹칠 수 없다.

 

- 이 경우 새로 만드는 버스 노선을 $\textrm{answer}$ 리스트에 추가해 주고, 방금 뽑은 버스 노선을 새로 만드는 버스 노선으로 갱신시켜 준다.

 

 

처음에는 $0$으로 가득 찬 배열을 누적 합 하듯 구현해 볼까 생각했었지만, 메모리도 많이 차지하고 시간도 부족할 것 같아 정렬하고 교체하는 방식으로 구현했다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 23740번 버스 노선 개편하기
# 그리디, 정렬
import sys
input = sys.stdin.readline

N = int(input())
li = sorted((tuple(map(int, input().rstrip().split())) for _ in range(N)), reverse = True)
now_S, now_E, now_C = li.pop()
ans = []
while li:
    S, E, C = li.pop()
    if S <= now_E:
        if E >= now_E:
            now_E = E
        if C < now_C:
            now_C = C
    else:
        ans.append((now_S, now_E, now_C))
        now_S, now_E, now_C = S, E, C
ans.append((now_S, now_E, now_C))
print(len(ans))
for tpl in ans:
    print(*tpl)