Algorithm/백준

[백준 알고리즘] 2002번: 추월 (Python)

에릭 Kim 2023. 12. 19. 15:48
반응형

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

 

2002번: 추월

입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이

www.acmicpc.net

 

소스코드

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
check = []
cnt = 0
enter = deque(input().strip() for _ in range(n))
out = deque(input().strip() for _ in range(n))

while out:
  if enter[0] in check:
    enter.popleft()
  else:
    k = out.popleft()
    if k != enter[0]:
      cnt += 1
      check.append(k)
    else:
      enter.popleft()
      
print(cnt)

 

풀이

★ 터널에 들어가는 순서와 나오는 순서가 다른 차들을 확인해주면서 추월한 차가 총 몇대인지 확인해줬습니다 ! 이 때 큐룰 사용하여 이미 확인한 차들은 큐에서 제거해줬습니다. 

 

★ 반복문은 나온 차들을 다 확인할 때까지 수행하는데, 들어간 차가 check라는 배열(추월한 차)에 있으면 확인할 필요가 없기에 제거해준 뒤 넘어갑니다. 아닌 경우, 나온 차와 들어간 차의 순서가 일치하는지  확인해줍니다 :)

반응형