백준 2002 추월 / python

문제 : 2002

풀이 point

이 문제를 풀 때 가장 착각하기 쉬운 요소는 들어올 때 뒤에 있던 차가 나갈 때는 앞에 갔다고 해서 추월했다는 알고리즘을 모든 차에 적용하는 것이다.

예제에서는 통하지만 다음 예제만 봐도 아니라는 것을 알 수 있다.

4
ABEEDF
EFDCEAC
AFDFDC
BBFDCCAD
BBFDCCAD
AFDFDC
EFDCEAC
ABEEDF

답 : 3

모든 차에 적용되지 않는 이유는 들어올 때 두번째였던 차가 나갈 때 세번째면 위의 알고리즘의 경우 추월을 하지 않았다고 판별하지만 실제로는 첫번째 차보다 빨리 나갔기 때문에 추월을 한 것이다.

때문에 해시 맵을 활용하여 자신의 앞에 있던 차가 자신보다 빨리 들어왔는지 늦게 들어왔는지를 통해 추월 여부를 판단할 수 있다. (빠른 위치 파악을 위해 해시맵을 활용하는 것이다.)

{차 이름 : 들어올 때 몇번째였는가}

풀이 코드

N = int(input())

outCar = {}
cars = []
cnt = 0

for idx in range(N):
  car = input()
  cars.append(car)

for idx in range(N):
  car = input()
  outCar[car] = idx

#idx = 들어올 때 몇번째 차
for idx in range(1, N): #첫번째 차는 추월이 불가능
  carNumber = cars[idx] #들어올 떄 차
  for i in range(idx):
    bCarNumber = cars[i]
    if outCar[bCarNumber] > outCar[carNumber]:
      cnt += 1
      break

print(cnt)