[백준] 2002번 추월 _ 문제 풀이

 


1. 문제

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

2. 풀이

ZG431SN : 0
ZG5080K : 1
ST123D : 2
ZG206A : 3
  • 들어가는 차 번호 문자열을 들어온 순서대로 번호를 매겨줍니다. (0, 1, 2, 3)
ZG206A : 3
ZG431SN : 0
ZG5080K : 2
ST123D : 1
  • 나오는 차 번호 문자열을 매겨진 번호를 확인하여 배열에 집어 넣습니다. (3, 0, 2, 1)
  • 배열에서 최소 값을 먼저 찾은 후에 앞에 있는 차들을 확인합니다. 앞에 있는 차들은 추월한차이기 때문에 정답에 추가해줍니다.
  • 위에서 찾은 최소 값 이후에 있는 값들을 기준으로 다시 최소값을 찾습니다. 최소 값을 찾을 수 없을 때 까지 다시 위의 과정을 반복해줍니다.
N = int(input())
dict = {}
arr = []
for i in range(N):
    dict[input()] = i
for i in range(N):
    arr.append(dict[input()])

start = 0
choowal = 0
while start < len(arr):
    min_val = min(arr[start:])
    min_idx = arr[start:].index(min_val) + start
    choowal += min_idx - start
    start = min_idx + 1
print(choowal)