파이썬(python) 백준 1966 : 프린터 큐

Python/백준 문제풀이

snowman95 2022. 9. 25. 18:38

728x90

collections 라이브러리에서 deque 를 큐로 사용하였습니다.
- 첫번째 요소를 추가/제거 하는 appendLeft(), popLeft() 메소드 지원
- 마지막 요소를 추가/제거 하는 append(), pop() 메소드 지원
- 모든 요소를 왼쪽/오른쪽 으로 회전시키는 rotate() 메소드 지원
Target(인쇄되는 순번이 궁금한 문서)의 index를 기억하기 위하여 튜플(우선순위, 0또는1) 형태로 변환해주었습니다.
Target 만 1입니다.
- zip() 함수를 이용하여 [1,2,3] [0,0,0] => [(1,0), (2,0), (3,0)] 형태로 묶을 수 있습니다.
- 이렇게 안하고 enumerate() 로 index 를 집어넣고 index가 m 인 요소인지로 판별해도 됩니다.
우선순위 오름차순 정렬 리스트를 따로 만들어서 마지막 요소와 출력할 리스트의 첫번재 문서와 우선순위 비교
- 같으면 출력할 list에서 popLeft(), 정렬 리스트 pop() 하고 출력수 1 증가
  - 튜플의 두번째 요소가 1로 되어있으면 Target으로 인식하고 프로그램 종료
- 다르면 list를 왼쪽으로 회전 시켜서 첫번재 요소를 마지막 위치로 이동.

쉬운 문제인데 이 문제로 얻어낸 인사이트가 있어서 포스팅 하였습니다.

deque이 아닌 list 사용했을 때 최종 수행 시간이 더 짧게 나옵니다.

deque 이라서 당연히 첫번째 요소를 제거하는 것이 O(1) 이니 list 보다 빠를 것이라고 생각했는데

문서의 크기가 최대 100개 이므로 사실 O(n) 이나 O(1) 이나 똑같은 수준이라서 큰 의미가 없는 것 같으며,

오히려 deque(list) 로 list를 deque 으로 변환하는 과정이 더 시간을 잡아 먹는 것 같습니다. (???)

제일 빠르게 푼 분들은 모두 list 로 구현하였고 코드 수행시간이 56ms 인데

deque 로 변환해서 돌려보면 92ms 로 상당히 큰 차이가 납니다.

따라서 n 의 범위가 넓지 않으면서 첫번째 요소 삭제가 있는 문제는

list + pop(index) > deque + popleft() 이렇게 되는 것 같습니다.

수행 속도 zip > range > enumerate 이다 ??

실제로 나는 zip으로 풀었고 대부분 사람들이 enumerate 으로 풀었길래 enumerate로 바꿨더니 오히려 더 느려졌습니다.

그래서 찾아보니 zip 이 enuerate 보다 10~20% 빠른 경향이 있다고 합니다. https://stackoverflow.com/a/52414411

또 다른 사람이 속도 개선 해서 포스팅 한 것이 있는데 이걸 봐도

range > enuerate 이고 zip > range 이다. 결국 속도는 zip > range > enuerate 순이라는 결론이 나옵니다.