[BOJ/Python] 백준 2002번 - 추월

백준 #2002 추월

2002번: 추월

import sys
input = sys.stdin.readline

n = int(input())   # 차의 대수
in_cars = {}
out_cars = []

for i in range(n):
  in_cars[input().strip()] = i
for _ in range(n):
  out_cars.append(input().strip())

cnt = 0   # 추월한 자동차 개수

for i in range(n-1):
  for j in range(i+1, n):
    if in_cars[out_cars[i]] > in_cars[out_cars[j]]:
      cnt += 1
      break
print(cnt)

나오는 차량 순서대로 들어올 때 인덱스를 본다. 나오는 차량의 들어올 때 인덱스가 이후 차량들의 들어올 때 인덱스보다 하나라도 클 경우 추월한 것으로 간주한다.

 

예를 들어 아래 예제의 경우

4
ZG431SN
ZG5080K
ST123D
ZG206A
ZG206A
ZG431SN
ZG5080K
ST123D

in_cars : {‘ZG431SN’ : 0, ‘ZG5080K’ : 1, ‘ST123D’ : 2, ‘ZG206A’ : 3}

out_cars : [ZG206A, ZG431SN, ZG5080K, ST123D]

와 같이 저장된다.

나오는 차량의 첫 번째 원소인 ZG206A은 들어올 때 인덱스가 3이다. 다음 차량인 ZG431SN은 들어올 때 인덱스가 1이다. ZG206A은 나올 때 첫 번째로 나왔지만 들어올 때는 세 번째로 들어온 것을 의미한다. 따라서 다른 차량을 추월한 것이다.