Algorithm/Baekjoon
[백준] 자료구조_2493, 17298, 2812, 10845, 2164, 10866, 1021, 1966
밍츠
2022. 9. 1. 09:51
탑
- 코드
n = int(input())
arr = list(map(int,input().split()))
stack = [] #최대값을 저장할 스택
result = [] #수신 탑 인덱스
for i in range(n):
while stack:
if stack[-1][1] > arr[i]:
result.append(stack[-1][0])
break
else:
stack.pop()
if not stack:
result.append(0)
stack.append([i+1,arr[i]])
print(' '.join(map(str,result)))
- 풀이를 생각해낸 과정
- 완전 탐색 - > 시간 초과
- stack에 마지막에 저장된 탑 높이와 비교하여 현재 탑보다 크면 result에 인덱스를 넣고, 작다면 스택에서 뺀다. (현재 탑에서 왼쪽 방향으로 가장 큰 탑을 찾기 때문)
- stack에서 현재 탑보다 큰 값을 찾거나 없다면 비워질 때 까지 반복한다.
- stack이 비워졌다면 현재 탑 높이보다 큰 값이 없기 때문에 result에 0을 넣는다.
- stack에 현재 탑의 인덱스+1, 높이 값을 저장한다. (다음 탑에서 비교할 땐 현재 탑의 높이도 비교 대상에 포함 되기 때문에)
- 시간복잡도 계산
- O(N) 보다 크고 O(N^2) 보다 작음
오큰수
- 코드
n = int(input())
arr = list(map(int,input().split()))
stack = []
result = []
for i in range(n-1, -1, -1):
while stack:
if stack[-1] > arr[i]:
result.append(stack[-1])
break
else:
stack.pop()
if not stack:
result.append(-1)
stack.append(arr[i])
print(" ".join(map(str,reversed(result))))
- 풀이를 생각해낸 과정
- 백준_탑 문제와 유사
- 배열의 마지막 원소부터 시작하여 stack에 마지막에 저장된 원소부터 현재 원소를 비교하여 현재 원소가 작다면 stack 마지막 값을 결과로 저장하고, 현재 원소가 크다면 stack 값을 비워가며 진행한다.
- stack에 값이 없다면 오큰수가 없다는 것으로 -1 값 저장
- stack에 현재 자신의 값 추가 (다음 원소에서는 현재 원소가 비교 대상으로 포함되기 때문에)
- 더 깔끔한 코드
import sys
n = int(input())
A = list(map(int, sys.stdin.readline().split()))
answer = [-1] * n
stack = []
stack.append(0)
for i in range(1, n):
while stack and A[stack[-1]] < A[i]:
answer[stack.pop()] = A[i]
stack.append(i)
print(*answer)
- 풀이
- stack에는 오큰수를 계산해야 하는 인덱스를 넣는다.
- answer에는 배열 크기만큼 -1을 넣는다.
- 먼저 stack에 0을 넣고 반복문을 1부터 진행한다.
- ex) 3 5 2 7 일 때,
- 3 < 5 → answer[0] = 5
- stack 1 추가
- 5 > 2 , stack 2 추가
- 2 < 7 → answer[2] = 7, 5 < 7 → answer[1] = 7
- stack 3 추가
- answer = [5, 7, 7, -1]
- 시간복잡도 계산
- O(N) 보다 크고 O(N^2) 보다 작음
크게 만들기
- 코드
n , k = map(int, input().split())
arr = list(input())
stack = []
count = 0
stack.append(arr[0])
for i in range(1,n):
while stack and stack[-1] < arr[i] and count<k:
stack.pop()
count+=1
stack.append(arr[i])
if count!=k:
print("".join(stack[:len(stack)-(k-count)]))
else:
print("".join(stack))
- 풀이를 생각해낸 과정
- 입력 받은 숫자를 오른쪽으로 이동하며 stack에 있는 값과 해당 숫자를 비교한다.
- stack에서 뺄 때 count 개수도 증가 시킨다
- stack에는 count가 k 보다 작을 때까지 기준으로 만들 수 있는 가장 큰 수가 저장 된다
- ex ) n = 6 k =2 arr = 222221 일 때 for문에서 stack의 값은 [’2’,’2’,’2’,’2’,’2’] 이다. 그래서 count가 k개가 아닐 때를 따로 인덱싱 처리해준다. (뒤를 자를 수 있는 이유는 큰 수가 앞에 가 있기 때문)
- 시간복잡도 계산
- O(N) 이상 O(N^2) 이하
큐 2
- 코드
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
queue = deque()
for i in range(n):
cmd = input().split()
length = len(queue)
if cmd[0] == "push":
queue.append(cmd[1])
if cmd[0] == "pop":
if length == 0:
print(-1)
else:
print(queue.popleft())
if cmd[0] == "size":
print(length)
if cmd[0] == "empty":
if length == 0:
print(1)
else:
print(0)
if cmd[0] == "front":
if length == 0:
print(-1)
else:
print(queue[0])
if cmd[0] == "back":
if length == 0:
print(-1)
else:
print(queue[-1])
- 풀이를 생각해낸 과정
- collections 모듈의 deque를 이용하여 큐 구현
- len() , 인덱싱 사용 가능
- popleft() : 큐의 첫 번째 데이터 제거
- 시간복잡도 계산
- O(N)
큐
- 코드
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
queue = deque()
for i in range(n):
cmd = input().split()
length = len(queue)
if cmd[0] == "push":
queue.append(cmd[1])
if cmd[0] == "pop":
if length == 0:
print(-1)
else:
print(queue.popleft())
if cmd[0] == "size":
print(length)
if cmd[0] == "empty":
if length == 0:
print(1)
else:
print(0)
if cmd[0] == "front":
if length == 0:
print(-1)
else:
print(queue[0])
if cmd[0] == "back":
if length == 0:
print(-1)
else:
print(queue[-1])
- 풀이를 생각해낸 과정
- 큐2와 같은 문제지만, 이 문제는 시간 제한이 0.5초
- 시간복잡도 계산
- O(N)
카드 2
- 코드
from collections import deque
n = int(input())
lst = [i for i in range(1,n+1)]
queue = deque(lst)
while len(queue) >= 2:
queue.popleft()
queue.append(queue.popleft())
print(queue[0])
- 풀이를 생각해낸 과정
- 제일 위에 있는 카드를 버리는 연산 - popleft()
- 제일 위에 있는 카드를 제일 아래로 옮기는 연산 - popleft() 후 append
- len(queue) ≥1 로 하면 IndexError: pop from an empty deque
- 시간복잡도 계산
- O(N)
덱
- 코드
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
queue = deque()
for i in range(n):
cmd = input().split()
length = len(queue)
if cmd[0] == "push_front":
queue.appendleft(cmd[1])
if cmd[0] == "push_back":
queue.append(cmd[1])
if cmd[0] == "pop_front":
if length == 0:
print(-1)
else:
print(queue.popleft())
if cmd[0] == "pop_back":
if length == 0:
print(-1)
else:
print(queue.pop())
if cmd[0] == "size":
print(length)
if cmd[0] == "empty":
if length == 0:
print(1)
else:
print(0)
if cmd[0] == "front":
if length == 0:
print(-1)
else:
print(queue[0])
if cmd[0] == "back":
if length == 0:
print(-1)
else:
print(queue[-1])
- 풀이를 생각해낸 과정
- deque 맨 앞에 넣는 연산 : appendleft
- deque 맨 앞을 빼는 연산 : popleft
- 시간복잡도 계산
- O(N)
회전하는 큐
- 코드
from collections import deque
n, m = map(int,input().split())
arr = list(map(int,input().split()))
lst = [i for i in range(1,n+1)]
queue = deque(lst)
result = []
count = 0
for i in range(len(arr)):
k = queue.index(arr[i])
if (len(queue)//2) +1 > k :
while queue[0] != arr[i]:
queue.append(queue.popleft())
count+=1
else:
while queue[0] != arr[i]:
queue.appendleft(queue.pop())
count+=1
queue.popleft()
print(count)
- 풀이를 생각해낸 과정
- 찾으려는 원소의 인덱스 위치가 queue 길이의 절반+1을 기준으로 왼쪽에 있다면 왼쪽 이동 연산, 오른쪽에 있다면 오른쪽 이동 연산은 수행한다.
- queue 길이의 절반+1, 여기서 +1을 하지 않으면 오른쪽 연산은 자신을 앞으로 옮기는 연산까지 포함되어 최소 연산을 보장하지 못한다.
- 시간복잡도 계산
- O(M*N)
프린터 큐
- 코드
import sys
from collections import deque
input = sys.stdin.readline
test = int(input())
for i in range(test):
case = input().split()
arr = list(map(int,input().split()))
queue = deque(arr)
temp = [j for j in range(int(case[0]))]
sequeue = deque(temp)
count = 0
while True:
if queue[0] == max(queue):
if sequeue[0] == int(case[1]):
count+=1
print(count)
break
else:
queue.popleft()
sequeue.popleft()
count+=1
else:
queue.append(queue.popleft())
sequeue.append(sequeue.popleft())
- 풀이를 생각해낸 과정
- 중요도를 저장하는 queue와 중요도에 해당하는 인덱스를 저장하는 sequeue를 변수로 활용
- queue의 첫 번째 값이 queue에서 가장 큰 값인 경우와 아닌 경우로 나누어서,
- 가장 큰 값인 경우
- 그 값의 순서가 찾고 싶은 문서와 같은 경우 → count 출력
- 아닌 경우 → 맨 앞의 원소 빼냄
- 가장 큰 값이 아닌 경우
- 맨 앞의 원소를 빼서 뒤로 보냄
- 가장 큰 값인 경우
- 시간복잡도 계산