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()
Author And Source
이 문제에 관하여(2002 추월), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lky9303/2002-추월저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)