[BOJ] Python 백준 23740번 버스 노선 개편하기 골드 5

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

23740번: 버스 노선 개편하기

문제 풀이

---

눈여겨봐야 할 점은 3가지다.

 

1. 버스 노선의 개수인 N은 20만 이하이다.
2. 한 점 이상에서 겹쳐지면 연장 가능한 노선이다.
3. 개편된 노선의 요금은 개편할 때 사용된 노선의 최소 요금을 적용한다.

 

문제와 그림을 보고 바로 떠오른 생각은 노선의 정보를 오름차순으로 정렬한 뒤 개편된 노선과 겹친다면 포함하는 노선, 겹치는 부분이 없다면 새로운 개편된 노선으로 판단하는 방식이다.

 

이 방식대로 연산하면 Sort를 이용하여 정렬할 때 O(nlogn), 오름차순 된 노선 정보를 처음부터 훑을 때 O(n)으로 총 O(nlogn)의 시간 복잡도가 걸린다고 생각했다.

 

따라서 소스 코드는 다음과 같다.

 

n=int(input())
bus=[]
res=[]
for i in range(n):
    bus.append(list(map(int,input().split())))
bus.sort(key=lambda x:(x[0],x[1]))
check=True
for i in bus:
    if check:
        res.append(i)
        check=False
    else:
        if i[0]<=res[len(res)-1][1]:
            if i[1]>res[len(res)-1][1]:
                res[len(res)-1][1]=i[1]
            if res[len(res)-1][2]>i[2]:
                res[len(res)-1][2]=i[2]
        else:
            res.append(i)
print(len(res))
for i in res:
    print(i[0],i[1],i[2])

 

bus는 기존 노선 정보를 저장하고 res는 개편된 노선 정보를 저장할 리스트이다.

 

6번째 줄에서 lambda를 키로 이용하여 0번째 원소, 1번째 원소를 기준으로 오름차순 정렬한다는 뜻이다.

 

check 변수를 통해 첫 노선을 개편된 노선으로 잡았고 겹치는 부분이 있을 경우로 나눠 14번째 if문은 현재 노선 정보가 개편된 노선보다 길어서 연장해야 될 때, 16번째 if문은 최소 요금으로 갱신하는 문장이다.

 

또한 겹치는 부분이 없으면 기존 노선을 개편된 노선으로 추가한다.

 

한 줄씩 원리를 따라가 보면 쉽게 이해할 수 있을 것이다.

 

결과 화면

 

Python으로 제출하면 시간 초과가 뜨길래 PyPy로 제출했더니 통과했다.

 

PyPy는 한 줄씩 해석하는 인터프리터 방식인 Python의 느린 동작에서 컴파일 방식을 개선하여 나온 언어로 상당히 빠른 수행 속도가 특징이다.

 

따라서 동일한 문법이기에 애초에 시간 복잡도를 비효율적으로 작성한 경우가 아니라면 Python으론 시간 초과 뜨는 코드가 PyPy로 통과하는 경우가 많다.

 

즉 올바르게 작성한 것 같은데 시간 초과가 뜬다면 PyPy로 제출하길 추천한다.