2002 추월

골4

queue로 구현하면 거의 실4 까지 난이도가 떨어질 수 있을 것 같다.

문제가 간단해서 처음엔 왜 골드인지 이해가 안됐다.

하지만 해시를 이용해서 풀 경우 난이도가 올라갈 것 같다.

풀이

들어오는 차마다 queue에 넣어주고, 터널 밖으로 나오는 차가 해당 queue에서 0번째 인덱스에 있는 차와 일치하는지 확인한다.

일치하다면 정상적으로 차선을 달린것이기 때문에, 그냥 큐에서 제거해준다.

일치하지 않는다면 그 차는 추월을 한 차이기 때문에 카운트를 더해주고, 기존 큐에서 값을 삭제해준다.

O(n^2) 의 시간복잡도를 갖지만 n의 수가 1000이 최대이기 때문에 시간초과가 발생하지 않는다.

N = int(input())

def solution():
    queue = []
    count = 0
    for _ in range(N):
        queue.append(input())

    while queue:
        temp = input()
        if queue[0] != temp:
            count += 1
            queue.remove(temp)
        else:
            del queue[0]
    print(count)

solution()