https://acmicpc.net/problem/2002

풀이

처음에 문제 이해를 잘못해서 그냥 들어온 순서보다 나간 순서 값이 더 작으면 추월한다고 짜줬었는데 틀려서 생각해보니 추월한 차가 많아지면 들어온 순서보다 나간 순서 값이 더 작지 않더라도 추월한 경우가 있을 것이라는 걸 깨달았다. 즉 상대적인 위치를 생각해줘야 한다.

그래서 지금 나온 차량의 들어온 순서와 지금 나온 차량보다 늦게 나온 차량의 들어온 순서를 비교해줬다. 이를 위해서 딕셔너리를 사용해서 key값을 차량번호, value값을 순서로 두고 들어간 순서에 대한 딕셔너리와 나온 순서에 대한 딕셔너리를 각각 만들었고, 이중 반복문을 써서 비교해줬다.

코드

N = int(input())
# 딕셔너리에 차번호:순서 형태로 저장
in_cars = {}
out_cars = {}

for i in range(N):
    car = input()
    in_cars[car] = i

for i in range(N):
    car = input()
    out_cars[car] = i

count = 0
out_keys = list(out_cars.keys())
# 지금 나온 차의 들어간 순서보다 나중에 나온 차의 들어간 순서가 앞인 경우에는 추월
for i in range(0, len(out_keys)-1):
    now_in = in_cars[out_keys[i]]
    for j in range(i+1, len(out_keys)):
        next_in = in_cars[out_keys[j]]
        if next_in < now_in:
            count += 1
            break

print(count)