728x90
반응형
- 문제
- 잘못된 풀이
import sys
N = int(sys.stdin.readline())
num_list = [i for i in range(1,N+1)]
# print(num_list)
while len(num_list) > 1:
num_list.pop(0) # 맨 위에 있는 원소 pop
number = num_list.pop(0) # 두번째 있는 원소 pop하고 마지막에 붙이기
num_list.append(number)
if len(num_list) == 1:
print(num_list[0])
나는 해당 문제를 queue의 자료구조를 생각하며 풀었다.
문제는 쉽게 풀 수 있었지만, 결과적으로 시간초과로 문제풀이에 실패하였다.
- 올바른 풀이
import sys
from collections import deque
N = int(sys.stdin.readline())
deque = deque([i for i in range(1, N+1)])
while len(deque) > 1:
deque.popleft()
number = deque.popleft()
deque.append(number)
print(deque[0])
queue의 자료구조 방법으로 해당 문제 풀이에 실패하였기 때문에,
queue보다 더 낮은 시간복잡도를 가지는 방법으로 문제를 해결해야 한다.
Collections, deque (Double Ended Queue) ?
파이썬에서 제공하는 모듈 중에, collections의 deque가 있다.
queue와 stack을 모두 만들 수 있는 자료구조로, 양 끝에서 모두 push와 pop이 가능하다.
deque는 CPython으로 구성되어 있기 때문에, queue보다 훨씬 빠르다.
이렇게 queue보다 빠른 deque로 문제를 해결할 수 있었다.
728x90
'자료구조 및 알고리즘 > 백준' 카테고리의 다른 글
[python] 1966. 프린터 큐 (0) | 2023.02.02 |
---|---|
[python] 4949. 균형잡힌 세상 (0) | 2023.01.30 |
[python] 10866. 덱 (0) | 2023.01.27 |
[python] 10845. 큐 (0) | 2023.01.27 |
[python] 10828. 스택 (0) | 2023.01.27 |