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

인프런 커뮤니티 질문&답변

이희종

작성한 질문수

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

7. 교육과정설계(큐)

작성

288

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도 동일하게 사용 가능한데 큐를 사용하는 이유가 궁금합니다.

python 코딩-테스트

답변 1

김태원

지식공유자

안녕하세요^^

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

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

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

이희종

작성한 질문수

전체 Q&A

질문하기