큐

import sys from collections import deque input = sys.stdin.readline q = deque() for _ in range(int(input())): command = input().rstrip() if command == "pop": print(-1 if len(q) == 0 else q.popleft()) elif command == "size": print(len(q)) elif command == "empty": print(+(not q)) elif command == "front": print(-1 if len(q) == 0 else q[0]) elif command == "back": print(-1 if len(q) == 0 else q[-1])..

import sys from collections import deque input = sys.stdin.readline n = int(input()) q = deque([i for i in range(1, n+1)]) while len(q)!=1: q.popleft() q.append(q.popleft()) print(q[0]) 큐로 풀면 되는 아주 간단한 문제다 시간 복잡도 deque는 double-linked list로 구현되어 있음 그래서 양 끝의 요소의 추가/삭제가 O(1)을 만족 반면, Python의 list는 fixed size memory blocks(array)로 구현되어 있음. 링크드 리스트처럼 보이지만 고정된 사이즈의 메모리를 갖는 array 따라서 리스트의 마지막 원소 삭제는 O(1..

def solution(numbers): answer = [-1] stack = [numbers[-1]] for i in range(len(numbers)-2, -1, -1): while stack and stack[-1] numbers[i-1]: stack.append(numbers[i]) answer.reverse() return answer 백준-탑 문제와 유사하다. stack에 큰 숫자들을 쌓는다. 현재 top보다 큰 숫자가 나오면 pop()을 해준다. 스택이 비어있으면, 현재 숫자보다 큰 숫자가 뒤에 없었다는 뜻이므로 -1을 넣어준다. 스택이 남아 있다면, 현재 숫자의 뒤에 있는 큰 수는 top 이다. 그리고 마지막에 현재 값도 넣어주는데, 현재 값이 다음 값보다는 큰 수일 수 있기 때문이다. ..