[Algorithm] 스택, 큐

알고리즘 스터디

Jun 29, 2023

Contents

Problem

Day	Date	No.	Problem	From	Level	Time	Redo
01	2023-06-23	001	[큐, 덱] 프린터 큐	BOJ	`Silver`	ㅤ	ㅤ
ㅤ	ㅤ	002	[큐, 덱] 큐 2	-	`Silver`	ㅤ	ㅤ
02	2023-06-24	003	[큐, 덱] 회전하는 큐	-	`Silver`	ㅤ	✓
ㅤ	ㅤ	004	[큐, 덱] AC	-	`Gold`	ㅤ	ㅤ
03	2023-06-27	005	[스택2] 오큰수	-	`Gold`	ㅤ	ㅤ
ㅤ	ㅤ	006	[스택2] 오동큰수	-	`Gold`	ㅤ	ㅤ
04	2023-06-28	007	[스택2] 문자열 폭발	-	`Gold`	ㅤ	ㅤ
ㅤ	ㅤ	008	[스택2] 히스토그램	-	`Platinum`	ㅤ	✓
05	2023-06-29	009	[스택/큐] 같은 숫자는 싫어	Prgm	`lv.1`	4’	ㅤ
ㅤ	ㅤ	010	[스택/큐] 기능개발	-	`lv.2`	ㅤ	✓
06	2023-06-29	011	[스택/큐] 올바른 괄호	-	`lv.2`	20’	ㅤ
ㅤ	ㅤ	012	[스택/큐] 프로세스	-	`lv.2`	13’	ㅤ
ㅤ	ㅤ	013	[스택/큐] 다리를 지나는 트럭	-	`lv.2`	ㅤ	✓
ㅤ	ㅤ	014	[스택/큐] 주식가격	-	`lv.2`	ㅤ	✓

Day 01 ~ 05 : 파이썬 알고리즘 인터뷰(개념) + BOJ 문제 풀이 (자율)

Day 06 : 프로그래머스 문제 풀이 (6문제 / 시간제한 2시간)

Solution

01. [큐, 덱] 프린터 큐


# [BOJ 1966] 프린터 큐

from collections import deque
import sys
input = sys.stdin.readline

케이스 = int(input())
for _ in range(케이스):
    _, target_idx = map(int, input().split())
    queue = deque(map(int, input().split()))
    cnt = 0

    while target_idx >= 0:
        # 맨 앞 숫자가 가장 높은 경우 빼준다. > 길이가 하나 줄어든 queue가 만들어진다.
        if queue[0] == max(queue):
            queue.popleft()
            target_idx -= 1
            cnt += 1

        # 아닐 경우 rotate 시킨다
        else :
            queue.rotate(-1)
            # target: target_idx==0이면 맨 뒤로 이동, !=0이면 한 칸 앞으로 이동
            target_idx += (-1 if target_idx else len(queue)-1)
    print(cnt)

02. [큐, 덱] 큐 2


# [BOJ 18258] 큐 2

import sys
from collections import deque
input = sys.stdin.readline
queue = deque()

N = int(input())
for _ in range(N):
    cmd = input().split()

    if cmd[0] == "push":
        queue.append(cmd[1])
    elif cmd[0] == "pop":
        print(queue.popleft() if queue else -1)
    elif cmd[0] == "size":
        print(len(queue))
    elif cmd[0] == "empty":
        print(int(len(queue)==0))
    elif cmd[0] == "front":
        print(queue[0] if queue else -1)
    else :
        print(queue[-1] if queue else -1)

03. [큐, 덱] 회전하는 큐

04. [큐, 덱] AC


# [BOJ 5430] AC
from collections import deque
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    cmd = input()
    n = int(input())
    queue = deque(eval(input()))
    R_cnt = 0

    try:
        for c in cmd:
            if c=="R":
                R_cnt+=1
            elif c=="D":
                queue.popleft() if R_cnt%2==0 else queue.pop()
        if R_cnt%2==1:
            queue.reverse()
        print("[" + ",".join(map(str, queue)) + "]")
    except:
        print("error")

05. [스택2] 오큰수


# [BOJ 17298] 오큰수

N = int(input())
nums = list(map(int, input().split()))
answer = [-1] * N
stack = [0]

for i in range(N):
    while stack and nums[stack[-1]] < nums[i]:
        answer[stack.pop()] = nums[i]
    stack.append(i)

print(*answer)

06. [스택2] 오동큰수

07. [스택2] 문자열 폭발


# [BOJ 9935] 문자열 폭발

string = input()
bomb = input()
stack = []

for ch in string:
    # string에 있는 글자를 하나씩 stack에 넣는다.
    stack.append(ch)

    # 넣은 글자가 bomb_fin과 같을 경우, bomb_len 길이만큼 이전에 stack에 넣은 글자도 확인한다.
    # bomb이 맞을 경우 제거한다.
    if (ch == bomb[-1]) and ("".join(stack[-len(bomb):])==bomb):
        for _ in range(len(bomb)):
            stack.pop()

remain = "".join(stack)
print(remain or "FRULA")

08. [스택2] 히스토그램

09. [스택/큐] 같은 숫자는 싫어


# [프로그래머스 12906번] 같은 숫자는 싫어
# 4min

def solution(arr):
    stack = [arr[0]]
    for i in arr:
        if stack[-1]!=i:
            stack.append(i)
    return stack

10. [스택/큐] 기능개발


# [BOJ 1966] 프린터 큐
from collections import deque
import sys
input = sys.stdin.readline

케이스 = int(input())
for _ in range(케이스):
    _, target_idx = map(int, input().split())
    queue = deque(map(int, input().split()))
    cnt = 0

    while target_idx >= 0:
        # 맨 앞 숫자가 가장 높은 경우 빼준다. > 길이가 하나 줄어든 queue가 만들어진다.
        if queue[0] == max(queue):
            queue.popleft()
            target_idx -= 1
            cnt += 1

        # 아닐 경우 rotate 시킨다
        else :
            queue.rotate(-1)
            # target: target_idx==0이면 맨 뒤로 이동, !=0이면 한 칸 앞으로 이동
            target_idx += (-1 if target_idx else len(queue)-1)
    print(cnt)

11. [스택/큐] 올바른 괄호


# [프로그래머스 12909번] 올바른 괄호
# 20min

def solution(s):
    stack = []
    for ch in s:
        # 이미 stack에 "("이 들어있고, 여기에 ")"를 추가하는 경우만 본다 > 가장 효율적
        if stack and ch==")" and stack[-1]=="(":
            stack.pop()
        else :
            stack.append(ch)
    return not bool(stack)

12. [스택/큐] 프로세스


# [프로그래머스 12909번] 올바른 괄호
# 13min

import collections
def solution(priorities, location):
    q = collections.deque(priorities)
    원래길이 = len(priorities)
    
    while len(q)>=location:
        if location==0 and q[0]==max(q):
            q.popleft()
            return 원래길이 - len(q)
            
        else:
            if q[0]==max(q):
                q.popleft()
                location -= 1
            else:
                q.rotate(-1)
                location -=1
            
        if location <0:
            location += len(q)

13. [스택/큐] 다리를 지나는 트럭


# [프로그래머스 42583번] 다리를 지나는 트럭
# 

from collections import deque

def solution(bridge_length, weight, truck_weights):
    time = 0
    on_bridge = [0] * bridge_length
    
    # 다리 위에도, 대기열에도 아무것도 없을 때까지 반복
    while len(truck_weights) or sum(on_bridge)>0:
        # 1) 시간이 1초 소요됨. 맨 앞에 있는 트럭은 빼준다.
        time += 1
        on_bridge.pop(0)
        
        # 2) 트럭 대기열이 남아있으면 > 제한무게를 넘지 않으면 넣고 아니면 건너뛴다(0을 넣는다)
        if truck_weights:
            if sum(on_bridge) + truck_weights[0] <= weight:
                on_bridge.append(truck_weights.pop(0))
            else:
                on_bridge.append(0)
        
    return time

14. [스택/큐] 주식가격


# [프로그래머스 42584번] 주식가격
# 

from collections import deque

def solution(prices):
    answer = []
    queue = deque(prices)
	
		# 기준보다 작은 수 중에 가장 오른쪽에 있는 것까지의 거리?    
    while queue:
        cnt = 0
        curr = queue.popleft()
        
        for p in queue:
            cnt += 1
            if curr > p:
                break
        
        answer.append(cnt)
    return answer

Contents

Problem Solution

# [BOJ 1966] 프린터 큐 from collections import deque import sys input = sys.stdin.readline 케이스 = int(input()) for _ in range(케이스): _, target_idx = map(int, input().split()) queue = deque(map(int, input().split())) cnt = 0 while target_idx >= 0: # 맨 앞 숫자가 가장 높은 경우 빼준다. > 길이가 하나 줄어든 queue가 만들어진다. if queue[0] == max(queue): queue.popleft() target_idx -= 1 cnt += 1 # 아닐 경우 rotate 시킨다 else : queue.rotate(-1) # target: target_idx==0이면 맨 뒤로 이동, !=0이면 한 칸 앞으로 이동 target_idx += (-1 if target_idx else len(queue)-1) print(cnt)

# [BOJ 18258] 큐 2 import sys from collections import deque input = sys.stdin.readline queue = deque() N = int(input()) for _ in range(N): cmd = input().split() if cmd[0] == "push": queue.append(cmd[1]) elif cmd[0] == "pop": print(queue.popleft() if queue else -1) elif cmd[0] == "size": print(len(queue)) elif cmd[0] == "empty": print(int(len(queue)==0)) elif cmd[0] == "front": print(queue[0] if queue else -1) else : print(queue[-1] if queue else -1)

# [BOJ 5430] AC from collections import deque import sys input = sys.stdin.readline T = int(input()) for _ in range(T): cmd = input() n = int(input()) queue = deque(eval(input())) R_cnt = 0 try: for c in cmd: if c=="R": R_cnt+=1 elif c=="D": queue.popleft() if R_cnt%2==0 else queue.pop() if R_cnt%2==1: queue.reverse() print("[" + ",".join(map(str, queue)) + "]") except: print("error")

# [BOJ 17298] 오큰수 N = int(input()) nums = list(map(int, input().split())) answer = [-1] * N stack = [0] for i in range(N): while stack and nums[stack[-1]] < nums[i]: answer[stack.pop()] = nums[i] stack.append(i) print(*answer)

# [BOJ 9935] 문자열 폭발 string = input() bomb = input() stack = [] for ch in string: # string에 있는 글자를 하나씩 stack에 넣는다. stack.append(ch) # 넣은 글자가 bomb_fin과 같을 경우, bomb_len 길이만큼 이전에 stack에 넣은 글자도 확인한다. # bomb이 맞을 경우 제거한다. if (ch == bomb[-1]) and ("".join(stack[-len(bomb):])==bomb): for _ in range(len(bomb)): stack.pop() remain = "".join(stack) print(remain or "FRULA")

# [프로그래머스 12909번] 올바른 괄호 # 20min def solution(s): stack = [] for ch in s: # 이미 stack에 "("이 들어있고, 여기에 ")"를 추가하는 경우만 본다 > 가장 효율적 if stack and ch==")" and stack[-1]=="(": stack.pop() else : stack.append(ch) return not bool(stack)

# [프로그래머스 12909번] 올바른 괄호 # 13min import collections def solution(priorities, location): q = collections.deque(priorities) 원래길이 = len(priorities) while len(q)>=location: if location==0 and q[0]==max(q): q.popleft() return 원래길이 - len(q) else: if q[0]==max(q): q.popleft() location -= 1 else: q.rotate(-1) location -=1 if location <0: location += len(q)

# [프로그래머스 42583번] 다리를 지나는 트럭 # from collections import deque def solution(bridge_length, weight, truck_weights): time = 0 on_bridge = [0] * bridge_length # 다리 위에도, 대기열에도 아무것도 없을 때까지 반복 while len(truck_weights) or sum(on_bridge)>0: # 1) 시간이 1초 소요됨. 맨 앞에 있는 트럭은 빼준다. time += 1 on_bridge.pop(0) # 2) 트럭 대기열이 남아있으면 > 제한무게를 넘지 않으면 넣고 아니면 건너뛴다(0을 넣는다) if truck_weights: if sum(on_bridge) + truck_weights[0] <= weight: on_bridge.append(truck_weights.pop(0)) else: on_bridge.append(0) return time

# [프로그래머스 42584번] 주식가격 # from collections import deque def solution(prices): answer = [] queue = deque(prices) # 기준보다 작은 수 중에 가장 오른쪽에 있는 것까지의 거리? while queue: cnt = 0 curr = queue.popleft() for p in queue: cnt += 1 if curr > p: break answer.append(cnt) return answer