[백준 2002번] 추월 - 파이썬

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

 

💡문제 분석 요약

터널에 들어가는 차의 순서와 터널에서 나오는 차의 순서를 알 때, 터널 안에서 추월한 차의 수를 구하여라.

 

💡알고리즘 설계

1. 터널에 들어가는 차 번호와 그 순서를 해시로 저장한다.

2. 터널에서 나오는 차 마다, 그 차보다 늦게 나오는 차와 들어갈 때 순서를 비교하여 자신 뒤에 자신보다 빨리 들어간 차가 있으면 추월 횟수를 1 늘린다.

 

💡코드

import sys
input = sys.stdin.readline

N=int(input())

in_order={}
for i in range(N):
    car=input().rstrip()
    in_order[car]=i

out_list=[]
for i in range(N):
    car=input().rstrip()
    out_list.append(car)

count=0

for i in range(N):
    for j in range(i+1, N):
        if in_order[out_list[i]]>in_order[out_list[j]]:
            count+=1
            break

print(count)

 

💡 느낀점 or 기억할 정보

처음에는 들어갈 때 차의 순서와 나올 때 차의 순서를 하나씩 비교해, 나올 때 차의 순서가 뒤로간 수를 셌는데, 순서가 같아도 자신 앞에 있던 차가 자신 뒤로 밀려날 경우 추월을 하게 된다.