[백준 10165번] 버스 노선 (Python3)

import sys
input = sys.stdin.readline
from collections import *

input(); N = int(input())
bus = []
for i in range(1,N+1):
  a,b = map(int,input().split())
  bus.append((a,-b,i))
bus.sort()
stack1 = deque(); stack2 = deque()
for a,b,i in bus:
  b = -b
  if a<b:
    if not stack1 or stack1[-1][1]<b:
      stack1.append((a,b,i))
  else:
    if not stack2 or stack2[-1][1]<b:
      stack2.append((a,b,i))
while stack1 and stack2:
  if stack1[0][1]<=stack2[-1][1]:
    stack1.popleft()
  elif stack1[-1][0]>=stack2[0][0]:
    stack1.pop()
  else:
    break
print(*sorted(i[2] for i in stack1+stack2))

스택을 이용하여 해결하였다.

 

풀이를 설명하면,

1. 버스노선을 출발지점이 작은 순으로 정렬한다. 출발지점이 같은 경우 도착지점이 큰 순으로 정렬한다.

2. 출발지점이 도착지점보다 큰 경우에는 stack1에, 출발지점이 도착지점보다 작은 경우에는 stack2에 담는다.

(이때 만약 스택의 마지막 노선의 도착지점보다 지금 도착지점이 작은 경우에는 포함된다는 뜻이므로 담지 않는다)

3. 스택1에서 스택2의 노선에 포함되는 노선을 제거한다. (포함관계를 생각해서 맨 처음과 끝 지점에서 하나씩 빼준다)

4. stack1과 stack2에 남아있는 노선들의 번호를 오름차순으로 출력한다.

 

원형노선이라는 점을 고려하여 출발지점과 도착지점의 대소관계만 고려하면 되는 간단한 스택문제이지만 1번 정렬과정에서 도착지점이 큰 순으로 정렬하지 않아서 틀렸습니다가 여러번 발생한 문제였다.

 

 

여담) 내 코드가 파이썬 기준 성능 1위가 되었다.