스택과 큐

스택

스택은 삽입과 삭제 연산이 후입선출로 이루어지는 자료구조이다. 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다.

위치

• top: 삽입과 삭제가 일어나는 위치를 뜻한다.

연산(리스트 이름이 s일 때)

• s.append(data): top 위치에 새로운 데이터를 삽입하는 연산이다.
• s.pop(): top 위치에 있는 데이터를 확인하고 삭제하는 연산이다.
• s[-1]: top 위치에 있는 데이터를 단순 확인하는 연산이다.

큐

큐는 삽입과 삭제 연산이 선입선출로 이뤄지는 자료구조이다. 스택과 다르게 먼저 들어온 데이터가 먼저 나간다. 삽입과 삭제가 양방향에서 이뤄진다.

위치

• rear: 큐에서 가장 끝 데이터를 가리키는 영역이다.
• front: 큐에서 가장 앞의 데이터를 가리키는 영역이다.

연산(리스트 이름이 s일 때)

• s.append(data): rear 부분에 새로운 데이터를 삽입하는 연산이다.
• s.popleft(): front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
• s[0]: 큐의 front 부분에 있는 데이터를 확인할 때 사용하는 연산이다.

우선순위 큐
우선순위 큐는 값이 들어간 순서와 상관 없이 우선순위가 놓은 데이터가 먼저 나오는 자료구조이다. 큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다. 우선순위 큐는 일반적으로 힙을 이용해 구현한다.

[백준] 오큰수 구하기 : 17298

문제

나의 풀이

스택 개념을 사용해서 크기를 비교하고, 결과가 확정된 인덱스는 pop해서 시간 복잡도를 줄였다.

import sys

n = int(input())
ans = [0]*n
a = list(map(int, input().split()))
mystack = []

for i in range(n):
    while mystack and a[mystack[-1]] < a[i]:
        ans[mystack.pop()] = a[i]
    mystack.append(i)

while mystack:
    ans[mystack.pop()] = -1

for i in range(n):
    sys.stdout.write(str(ans[i]) + " ")

print() 사용에 따른 런타임 에러

처음에는 마지막 부분을 아래와 같이 입력했는데 시간 초과, 런타임 에러가 났었다. 이 기회를 통해 print()와 sys.stdout.write()의 차이를 찾아봤다.

result = " "
for i in range(n):
    result += str(ans[i]) + " "
print(result)

끄적끄적

print()

print()는 매번 함수가 호출될 때마다 여러 처리(무자열 변환, 결합, 공백 추가 등)가 발생하고, 출력 버퍼를 비우는 작업까지 구행한다. 이 과정에서 I/O 비용이 커지며 실행시간이 늘어날 수 있다.

sys.stdout.write()

sys.stdout.write()는 문자열을 직접 출력하는 방식으로, 줄바꿈이나 공백을 추가하지 않는다. 또한, 버퍼링된 출력을 사용하여 한 번에 데이터를 출력할 수 있다. 따라서 이 방식은 매우 큰 데이터를 출력할 때, print()보다 훨씬 더 효율적일 수 있다.

출처: Do it! 알고리즘 코딩테스트 with Python