• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

교육과정설계 문제 관련 질문입니다.

23.05.15 18:30 작성 조회수 238

0

import sys
sys.stdin = open("input.txt", "rt")

a = input()
order = []

n = int(input())

course = ''
for TC in range(1, n+1):
   course = input()
   for x in a:
      order.append(x)

   for x in course:
      if x in order and x == order[0]:
         order.pop(0)
      elif x in order and x != order[0]:
         print("#%d NO" % TC)
         order.clear()
         break
   else:
      if len(order) != 0:
         order.clear()
         print("#%d NO" % TC)
      else:
         print("#%d YES" % TC)

문제를 풀이할 때 큐를 사용하지 않고 리스트만 사용해서 작성한 코드입니다.
리스트에서도 pop(0)으로 큐에서의 popleft()기능 수행이 가능하고 append도 동일하게 사용 가능한데 큐를 사용하는 이유가 궁금합니다.

답변 1

답변을 작성해보세요.

0

안녕하세요^^

효율성(시간복잡도)의 차이 때문입니다.

리스트는 배열 기반이기 때문에 pop(0)은 맨 앞에 자료를 꺼내고 그 뒤 자료들이 앞칸으로 한 칸씩 모두 이동을 하기 때문에 시간복잡도가 O(n)입니다.

하지만 deque의 링크드 리스트 기반이라서 popleft를 하면 앞 자료만 꺼내고 끝나므로 시간복잡도가 O(1)입니다.