추월

면접 대비

시간 제한2초메모리 제한128 MB

요약
차량들의 입장 순서와 퇴장 순서가 주어질 때 최장 공통부분수열에 포함되지 않는, 즉 추월이 있었던 차량 수를 구합니다.
난이도

쉬움10점 중 3점

유형
동적 계획법, 배열, 문자열
정답자
아직 제출이 없습니다

문제

대부분의 나라에서는 터널 안에서 차선을 바꾸는 것을 법으로 금지한다. 터널 안의 차선이 파선이 아니라 실선으로 그려져 있는 것도 같은 이유이다. 따라서 터널 내부에서는 차선을 바꾸어 앞차를 추월할 수 없다.

경찰인 대근이와 영식이는 터널 안에서 추월한 차량을 찾기 위해 한 터널을 감시했다. 대근이는 터널 입구에서 차량이 들어가는 순서대로 차량 번호를 기록했고, 영식이는 터널 출구에서 차량이 나오는 순서대로 차량 번호를 기록했다.

N대의 차량이 모두 지나간 뒤, 두 사람이 적은 목록을 비교하면 터널 안에서 반드시 추월했다고 볼 수 있는 차량의 수를 알 수 있다. 그 수를 구하는 프로그램을 작성하시오.

입력

입력은 총 2N+1개의 줄로 이루어진다.

첫째 줄에 차량의 수 N(1 <= N <= 1,000)이 주어진다. 다음 N개의 줄에는 대근이가 기록한 차량 번호가 터널에 들어간 순서대로 주어진다. 그 다음 N개의 줄에는 영식이가 기록한 차량 번호가 터널에서 나온 순서대로 주어진다.

각 차량 번호는 길이가 6 이상 8 이하인 문자열이며, 영어 대문자 A부터 Z와 숫자 0부터 9로만 이루어진다. 같은 차량 번호가 두 번 이상 주어지는 경우는 없다.

출력

터널 안에서 반드시 추월했다고 판단할 수 있는 차량의 수를 첫째 줄에 출력한다.

예제3

  1. 예제 1

    입력
    4
    ZG431SN
    ZG5080K
    ST123D
    ZG206A
    ZG206A
    ZG431SN
    ZG5080K
    ST123D
    
    예상 출력
    1
    
  2. 예제 2

    입력
    5
    ZG508OK
    PU305A
    RI604B
    ZG206A
    ZG232ZF
    PU305A
    ZG232ZF
    ZG206A
    ZG508OK
    RI604B
    
    예상 출력
    3
    
  3. 예제 3

    입력
    5
    ZG206A
    PU234Q
    OS945CK
    ZG431SN
    ZG5962J
    ZG5962J
    OS945CK
    ZG206A
    PU234Q
    ZG431SN
    
    예상 출력
    2