Stack, Queue, Deque

✍ 아래 문제를 풀어보자!

1. 첫번째 방법

Naive 하게 풀기
i 번째 기둥이 오른쪽에서 보이는가? -> O(N^2) -> 시간초과!

2. 두번째 방법

뒤에서부터 확인하기 -> O(N)

a = []
N = int(stdin.readline())
for i in range(N):
    a.append(int(stdin.readline()))
    
max = a[-1]
result = 1
for i in range(len(a)-2, -1, -1):
    if a[i] > max:
        result+=1
        max = a[i]

print(result)

3. 세번째 방법

앞에서부터 확인하기 -> Stack 사용

스택(Stack)

한쪽 끝에서만 원소를 넣고 뺄 수 있는 자료구조

• LIFO (Last In First Out)
• 데이터 삽입 삭제 O(1)
  
  
  

큐(Queue)

한 쪽에서는 원소를 넣고 다른 한쪽에서는 원소를 빼는 자료구조

• FIFO (First In First Out)
• 데이터 삽입 삭제 O(1)

선형큐 단점 : 삭제된 곳의 공간 낭비가 심함

원형큐로 해결!

덱(Deque)

스택 + 큐의 형태
양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조

✍ 위에서 배운 개념으로 아래 문제를 풀어보자!!

큐를 이용하면 된다.
참고로, 파이썬에서 큐를 쓰려면 deque 라이브러리를 사용하면된다.

from collections import deque
yose = deque()
N, K = map(int, stdin.readline().split())
for i in range(1, N+1):
    yose.append(i)

while len(yose) > 1:
    for _ in range(K-1):
        yose.append(yose.popleft())
    print(yose.popleft())
print(yose[0])