[백준 10615 파이썬] 버스 노선 그리디 알고리즘

문제

국경을 따라 순환 도로를 건설한 국가가 있다. 이 순환 도로에는 N개의 위치에 버스 정류소가 있으며, 버스 정류소에는 0부터 N-1까지 번호가 시계방향 순서로 지정되어 있다. 현재 여러 개의 버스 노선들이 이 순환 도로에서 운행되고 있다. 각 버스 노선은 [a,b]로 표시된다. 이 노선의 버스는 버스 정류소 a부터 b까지를 시계방향으로, b부터 a까지는 반시계방향으로 운행한다. 순환 도로 상의 모든 정류소를 포함하는 버스 노선은 존재하지 않는다. 

국가 교통행정부에서 비용 절감을 위해서 버스 노선 중 일부를 취소하려고 한다. 취소되는 노선은 다른 노선에 포함되어 있는 노선이다. 예를 들어, N=10일 때, 5개의 버스 노선이 다음과 같이 있다고 하자. 

[0, 4], [2, 6], [5, 0], [7, 9], [9, 4]

위 그림에서 버스 노선 ①은 ⑤에 포함되고, 버스 노선 ④는 ③에 포함된다. 버스 노선 ②, ③, ⑤를 포함하는 노선은 없다. 따라서 취소되는 버스 노선은 ①과 ④이다.

버스 노선에 대한 정보가 주어질 때, 취소되지 않고 계속 운행되는 버스 노선을 모두 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개의 줄에는 1번 노선부터 순서대로 각 버스 노선 [a,b]를 나타내는 두 개의 정수 a와 b가 한 줄에 주어진다, 단, 0 ≤ a, b ≤ N-1이고 a≠b이며 동일한 버스 노선이 두 번 이상 입력으로 주어지는 경우는 없다. 또한 순환 도로 상의 모든 정류소를 포함하는 버스 노선은 존재하지 않는다.

출력

입력으로 주어진 버스 노선들 중에서 다른 노선에 포함되지 않은 노선들의 번호를 번호가 작은 것부터 순서대로 빈칸을 사이에 두고 출력한다. 

풀이

버스 노선 중 전체 경로가 다른 노선에 포함되어 취소되는 노선을 제외한 나머지 노선을 제외해야한다.

버스 노선의 방향은 정방향과 역방향이 있다. 정방향은 시작번호가 끝나는번호보다 작은 경우고

역방향은 시작번호가 끝나는번호보다 더 큰 경우로 무조건 0을 지나간다.

 

첫번째 풀이에서,

역방향 버스는 무조건 0을 지나가고 정방향 버스는 0을 넘어갈 수 없기 때문에 다른 버스를 포함할 수 있는 경우는

정방향 버스가 정방향 버스를 포함,

역방향 버스가 역방향 버스를 포함,

역방향 버스가 정방향 버스를 포함

이 3가지 경우 밖에 없다.

따라서 입력값을 정렬하고 위 3가지 경우를 나누어 취소되는 버스번호를 찾는다.

 

두번째 풀이는 경우를 나누지않고

역방향 버스의 start에 n만큼 빼서 정방향 형태의 리스트를 만들고

end에 n만큼 더해서 정방향 리스트를 만든다.

이렇게 총 2개의 리스트를 생성하고

기존의 정방향 리스트와 새로 생긴 2개의 정방향으로 바꾼 역방향리스트를 비교한다. 

 

import sys
n = int(sys.stdin.readline().rstrip("\n"))
m = int(sys.stdin.readline().rstrip("\n"))
infosA=[]
infosB=[]
for i in range(m):
    start, end = map(int, sys.stdin.readline().rstrip("\n").split())
    if(start<end):
        infosA.append([start,end,i+1])
    elif(end<start):
        infosB.append([start,end,i+1])

infosA = sorted(infosA, key=lambda x:(x[0],-x[1]))
infosB = sorted(infosB, key=lambda x:(x[0],-x[1]))
#정방향-정방향
if(len(infosA)>0):
    stateA = infosA[0]
for i in range(1,len(infosA)):
    if(stateA[1]>=infosA[i][1]):
        infosA[i][2]=-1
    else:
        stateA = infosA[i]
#역방향-역방향
if(len(infosB)>0):
    stateB = infosB[0]
for i in range(1,len(infosB)):
    if(stateB[1]>=infosB[i][1]):
        infosB[i][2] = -1
    else:
        stateB = infosB[i]
#역방향-정방향
sB = infosB[0][0]
temp = sorted(infosB[:],key=lambda x:-x[1])
eB = temp[0][1]
for i in range(len(infosA)):
    if(infosA[i][0]>=sB or infosA[i][1]<=eB):
        infosA[i][2] = -1

ans = []
for i in range(len(infosA)):
    if(infosA[i][2]>0):
        ans.append(infosA[i][2])
for i in range(len(infosB)):
    if(infosB[i][2]>0):
        ans.append(infosB[i][2])
ans = sorted(ans)
for a in ans:
    print(a,end=" ")

 

2번째 풀이

import sys
n = int(sys.stdin.readline().rstrip("\n"))
m = int(sys.stdin.readline().rstrip("\n"))
infos1=[]
infos2=[]
for i in range(m):
    start, end = map(int, sys.stdin.readline().rstrip("\n").split())
    if(start>end):
        infos1.append([start-n,end,i+1])
        infos2.append([start,end+n,i+1])
    else:
        infos1.append([start,end,i+1])
        infos2.append([start,end,i+1])

infos1 = sorted(infos1, key=lambda x:(x[0],-x[1]))
infos2 = sorted(infos2, key=lambda x:(x[0],-x[1]))
exceptList=[]
check=[1]*(m+1)
state = infos1[0]
for i in range(1,m):
    if(state[1]>=infos1[i][1]):
        exceptList.append(infos1[i][2])
        check[infos1[i][2]] = 0
    elif(state[1]<infos1[i][1]):
        state=infos1[i]
state = infos2[0]
for i in range(1,m):
    if(state[1]>=infos2[i][1]):
        exceptList.append(infos2[i][2])
        check[infos2[i][2]] = 0
    elif(state[1]<infos2[i][1]):
        state=infos2[i]

for i in range(1,m+1):
    if(check[i]>0):
        print(i,end=" ")