BOJ 2002번: 추월

www.acmicpc.net/problem/2002

2002번: 추월

아이디어:

터널에 들어가기 전과 후의 차들의 이름을 배열에 각각 따로 저장한 후, while문을 돌면서 인덱스를 이용하여 구했다.

 

before idx와 after idx를 0 으로 초기화하고, 추월한 차들의 배열을 저장하는 car 을 set으로 선언하였다.

그림을 그리면서 정리하면 쉬웠다.

다만 처음에는 car을 배열이 아니라 그냥 한 변수로 설정했는데, 그러면 안되더라는 걸 알고.. 다음엔 queue를 사용하였는데 순서는 상관이 없다는 걸 또 알고.. 그냥 set으로 설정하니 통과하였다.

 

import sys
from collections import deque

N = int(sys.stdin.readline())
before = []
after = []
for _ in range(N):
    before.append(sys.stdin.readline().rstrip())
for _ in range(N):
    after.append(sys.stdin.readline().rstrip())

cnt = 0
bidx = 0
aidx = 0
car = set() #추월한 차량
while (True):
    if (aidx>N-1): break #after 배열을 모두 돌면 break
    if (before[bidx]==after[aidx]): #이름이 같은 경우 두 인덱스 모두 증가
        bidx+=1
        aidx+=1
        continue
    else: #이름이 다른 경우
        if (before[bidx] in car): #이미 추월했다고 저장한 배열안에 있으면
            car.remove(before[bidx]) #car에서 해당 원소를 지우고
            bidx+=1 #before idx++
            continue
        car.add(after[aidx]) #car에 추월한 차 추가
        cnt+=1 #카운트 증가
        aidx+=1 #after idx++
    
print(cnt)