[Stack, Queue, Deque] 💡 BOJ - 10828번, 9012번, 18258번, 1158번, 2164번, 10866번, 1935번, 1966번, 2346번, 1874번, 10799번, 2504번, 2800번, 2493번, 22942번, 1918번

자료구조별 연습

0️⃣ 스택

* LIFO

* 원소의 추가와 삭제가 O(1), 제일 상단이 아닌 나머지 원소들의 확인과 변경이 원칙적으로는 불가하다.

* 파이썬, 자바스크립트의 내장 array는 쉽게 스택처럼 동작할 수 있다. (append, pop / push, pop)

1️⃣ 큐

* FIFO

* 원소의 추가와 삭제, 제일 앞/뒤의 원소 확인이 O(1), 제일 앞/뒤가 아닌 나머지 원소들의 확인과 변경이 원칙적으로는 불가능하다. 

* 원소 변경에 따라 큐의 시작을 가리키는 head, 끝부분을 가리키는 tail이 재조정된다.

* 원형큐를 사용하면 큐에서의 삭제가 발생할 때마다 생기는 쓸모없는 공간의 낭비를 줄일 수 있다. 

* 파이썬에서는 deque을 활용하면 큐처럼 동작할 수 있다. 

from collections import deque

# 덱 객체 생성
a = deque()

# list를 deque으로 변환
a = deque([list])

# 덱 원소 삽입
a.append()
a.appendleft()

# 덱 원소 삭제
a.pop()
a.popleft()

2️⃣ 덱

* 덱은 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조이다

* 스택과 큐를 덱의 특수한 예시라고 생각해도 괜찮다.

* 원소의 추가와 삭제, 제일 앞/뒤 원소 확인이 O(1)이다. 

* 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능하다.

 

---

문제풀이

✅ 10828번 스택 (S4)

* 스택의 성격에 맞게 각각 함수를 처리해주면 쉽게 풀린다.

10828번: 스택

def getInput():
    N = int(input())
    return [list(input().split()) for _ in range(N)]

def push(stack, num):
    stack.append(num)

def pop(stack):
    if len(stack) == 0:
        print(-1)
        return
    print(stack.pop())

def size(stack):
    print(len(stack))

def empty(stack):
    if len(stack) == 0:
        print(1)
        return
    print(0)

def top(stack):
    if len(stack) == 0:
        print(-1)
        return
    print(stack[-1])
    
def solution():
    orders = getInput()
    stack = []
    for order in orders:
        if order[0] == 'push':
            push(stack, int(order[1]))
        elif order[0] == 'pop':
            pop(stack)
        elif order[0] == 'size':
            size(stack)
        elif order[0] == 'empty':
            empty(stack)
        elif order[0] == 'top':
            top(stack)


solution()

 

 

✅ 9012번 괄호 (S4)

* 괄호 문자열을 모두 읽었을 때 stack에 남은 괄호가 있다면 제대로 닫히지 않은 것이다.

9012번: 괄호

def getInput():
    N = int(input())
    return [input() for _ in range(N)]

def solution():
    pars = getInput()
    for par in pars:
        print(isVPS(par))

def isVPS(string):
    stack = []
    for s in string:
        if not stack:
            stack.append(s)
        elif s == '(':
            stack.append(s)
        elif s == ')' and stack[-1] == '(':
            stack.pop()
    if len(stack) > 0:
        return 'NO'
    return 'YES'


solution()

 

 

✅ 18258번 큐 2 (S4)

* 큐의 성격에 맞게 각각 함수를 처리해주면 쉽게 풀린다.

18258번: 큐 2

from collections import deque

def getInput():
    N = int(input())
    return [list(input().split()) for _ in range(N)]

def push(queue, num):
    queue.append(num)

def pop(queue):
    if len(queue) == 0:
        print(-1)
        return
    print(queue.popleft())

def size(queue):
    print(len(queue))

def empty(queue):
    if len(queue) == 0:
        print(1)
        return
    print(0)

def front(queue):
    if len(queue) == 0:
        print(-1)
        return
    print(queue[0])

def back(queue):
    if len(queue) == 0:
        print(-1)
        return
    print(queue[-1])

def solution():
    orders = getInput()
    queue = deque()
    for order in orders:
        if order[0] == 'push':
            push(queue, int(order[1]))
        elif order[0] == 'pop':
            pop(queue)
        elif order[0] == 'size':
            size(queue)
        elif order[0] == 'empty':
            empty(queue)
        elif order[0] == 'front':
            front(queue)
        elif order[0] == 'back':
            back(queue)


solution()

 

 

✅ 1158번 요세푸스 문제 (S4)

* O(n)으로 해결해야 한다. (N <= 5000)

1158번: 요세푸스 문제

from collections import deque

def getInput():
    n, k = map(int, input().split())
    return n, k

def print_result(arr):
    print("<", end="")
    length = len(arr)
    for i in range(length):
        if i == length - 1:
            print(f'{arr[i]}>')
            break
        print(f'{arr[i]},', end=" ")

def solution():
    n, k = getInput()
    result = []
    queue = deque()
    for i in range(1, n + 1):
        queue.append(i)

    while queue:
        for _ in range(k - 1):
            queue.append(queue.popleft())
        target = queue.popleft()
        result.append(target)

    print_result(list(result))


solution()

 

✅ 2164번 카드 2 (S4)

2164번: 카드2

from collections import deque

def getInput():
    return int(input())

def solution():
    n = getInput()
    queue = deque()
    for i in range(n, 0, -1):
        queue.append(i)
    while len(queue) > 1:
        queue.pop()
        queue.appendleft(queue.pop())
    return queue.pop()

print(solution())

 

✅ 10866번 덱 (S4)

10866번: 덱

from collections import deque

def getInput():
    N = int(input())
    return [list(input().split()) for _ in range(N)]

def push_front(d, num):
    d.appendleft(num)

def push_back(d, num):
    d.append(num)

def pop_front(d):
    if len(d) == 0:
        print(-1)
        return
    print(d.popleft())

def pop_back(d):
    if len(d) == 0:
        print(-1)
        return
    print(d.pop())

def size(d):
    print(len(d))

def empty(d):
    if len(d) == 0:
        print(1)
        return
    print(0)

def front(d):
    if len(d) == 0:
        print(-1)
        return
    print(d[0])

def back(d):
    if len(d) == 0:
        print(-1)
        return
    print(d[-1])

def solution():
    orders = getInput()
    d = deque()
    for order in orders:
        if order[0] == 'push_front':
            push_front(d, int(order[1]))
        elif order[0] == 'push_back':
            push_back(d, int(order[1]))
        elif order[0] == 'pop_front':
            pop_front(d)
        elif order[0] == 'pop_back':
            pop_back(d)
        elif order[0] == 'size':
            size(d)
        elif order[0] == 'empty':
            empty(d)
        elif order[0] == 'front':
            front(d)
        elif order[0] == 'back':
            back(d)
            

solution()

 

✅ 1935번 후위 표기식2 (S3)

* 순서가 보장된 OrderedDict 이용

from collections import OrderedDict

ordered_dic = OrderedDict()
ordered_dic['A'] = 1
ordered_dic['B'] = 2
ordered_dic['C'] = 3  // OrderedDict([('A', 1), ('B', 2), ('C', 3)])

for key, val in ordered_dic.items():
    print(key, val) // A 1 \n B 2 \n C 3

isinstance(ordered_dic, dict)  // True

* 후위 표기식은 피연산자일 때는 스택에 담고, 연산자일 때는 꺼내서 연산해준 후 다시 넣으면 쉽게 계산할 수 있다. 

* 자릿수 맞추는 것은 f 스트링을 이용해서 표현해주면 된다.

1935번: 후위 표기식2

from collections import OrderedDict
operators = ['*', '+', '-', '/']

def getInput():
    n = int(input())
    line = input()
    d = OrderedDict()
    for s in line:
        if s not in operators:
            d[s] = 0
    for key in d.keys():
        d[key] = int(input())
    return d, line

def solution():
    d, line = getInput()
    stack = []
    for s in line:
        if s not in operators:
            stack.append(d[s])
            continue
        operand2 = stack.pop()
        operand1 = stack.pop()
        stack.append(calculate(operand1, operand2, s))
    return f'{stack.pop():.2f}'

def calculate(operand1, operand2, symbol):
    if symbol == '+':
        return operand1 + operand2
    if symbol == '*':
        return operand1 * operand2
    if symbol == '-':
        return operand1 - operand2
    if symbol == '/':
        return operand1 / operand2


print(solution())

 

 

✅ 1966번 프린터 큐 (S3)

1966번: 프린터 큐

from collections import deque

def print_result(arr):
    for el in arr:
        print(el)

def solution():
    result = []
    num_case = int(input())
    for _ in range(num_case):
        n, idx = list(map(int, input().split()))
        arr = list(map(int, input().split()))

        if n == 1:  # early return
            result.append(1)
            continue

        for i in range(len(arr)):
            if i == idx:  # 타깃 인덱스 기억
                arr[i] = [arr[i], True]
                continue
            arr[i] = [arr[i], False]

        d = deque(arr)
        cnt = 1
        while True:
            if len(d) == 0:
                break
            arr = [curr[0] for curr in d]
            max_value = max(arr)
            curr = d.popleft()
            if curr[1] and curr[0] >= max_value:  # 타깃 넘버고 최댓값일 때 종료
                break
            if curr[0] < max_value:
                d.append(curr)
                continue
            cnt += 1
        result.append(cnt)
    print_result(result)


solution()

 

 

✅ 2346번 풍선 터뜨리기 (S3)

* 요세푸스 문제와 유사하다. 원형으로 돌기 위해 덱을 이용하자! 

2346번: 풍선 터뜨리기

from collections import deque


def getInput():
    n = int(input())
    nums = list(map(int, input().split()))
    balls = [[nums[i], i + 1] for i in range(len(nums))]
    return n, balls

def print_result(arr):
    for s in arr:
        print(s, end=" ")

def solution():
    n, balls = getInput()
    result = []
    d = deque(balls)

    skip, idx = d.popleft()  # 첫 번째 풍선
    result.append(idx)
    while d:
        if skip >= 0:
            for _ in range(skip - 1):
                d.append(d.popleft())
            skip, idx = d.popleft()
            result.append(idx)
        else:
            for _ in range(-skip - 1):
                d.appendleft(d.pop())
            skip, idx = d.pop()
            result.append(idx)
    print_result(result)


solution()

 

 

✅ 1874번 스택 수열 (S2)

* 동작이 헷갈린다면 시뮬레이션해 살펴보자.

1874번: 스택 수열

def getInput():
    n = int(input())
    target = [int(input()) for _ in range(n)]
    return n, target

def solution():
    n, target = getInput()
    stack = []
    process = []
    sequence = []
    curr_idx = 0  # 0 ~ (n - 1)까지, 순열에서 맞춰야 하는 수
    curr_num = 1  # 현재 넣는 숫자 기준

    while True:  # 순차적이지 않은 조건에서 break로 종료 조건을 제어 해주는 게 편한 경우
        if curr_num > n:
            while stack:
                pop(stack, process, sequence)
            break
        # 🚨 조건 순서에 따라 실수하기 쉬우니 continue 문을 쓸 때는 주의하자
        if stack and target[curr_idx] == stack[-1]:  
            pop(stack, process, sequence)
            curr_idx += 1
            continue
        if target[curr_idx] == curr_num:
            push(stack, process, curr_num)
            pop(stack, process, sequence)
            curr_idx += 1
            curr_num += 1
            continue
        if target[curr_idx] != curr_num:
            push(stack, process, curr_num)
            curr_num += 1
            continue

    if is_possible_sequence(sequence, target):
        for s in process:
            print(s)
    else:
        print('NO')

def push(stack, process, elem):
    stack.append(elem)
    process.append('+')

def pop(stack, process, sequence):
    sequence.append(stack.pop())
    process.append('-')

def is_possible_sequence(sequence, target):
    for i in range(len(target)):
        if sequence[i] != target[i]:
            return False
    return True


solution()

 

 

✅ 10799번 쇠막대기 (S2)

* 특정 구조에서는 특정한 성질을 가질 수 있다. 

* 규칙이 있으면 규칙발견, 일반화를 위해 시뮬레이션 해보자

10799번: 쇠막대기

def getInput():
    return input()

def count_iron(line):
    cnt = 0
    for i in range(len(line)):
        if line[i] == '(' and line[i + 1] != ')':
            cnt += 1
    return cnt

def solution():
    line = getInput()
    # 연속된 '(', ')' 제외하고 나오는 '('가 개수 -> func: count_iron
    # 하나의 레이저가 자를 수 있는 막대기 수 세기 -> 스택에 남아있는 여는 괄호 개수가 걸쳐 있는 쇠 막대기 개수와 동일
    total_irons = count_iron(line)
    stack = []
    for i in range(len(line)):
        curr = line[i]
        if not stack:
            stack.append(curr)
        elif curr == '(':
            stack.append(curr)
        elif curr == ')' and line[i - 1] == '(':  # 레이저인 경우
            stack.pop()
            total_irons += len(stack)
        elif curr == ')' and stack[-1] == '(':
            stack.pop()
    return total_irons


print(solution())

 

✅ 2504번 괄호의 값 (G5)

2504번: 괄호의 값

def getInput():
    return input()

def solution():
    d = {'(': 2, '[': 3, ')': 2, ']': 3}
    string = getInput()

    if not is_valid_form(string, d):
        return 0

    # ✔️이전 상태 복원의 아이디어
    # 여는 괄호를 만나면 temp 값에 *n
    # 닫는 괄호를 만나면 temp 값이 //n (이전 상태 복원)
    # 이전 값이 여는 괄호일 때만 더하기

    temp = 1
    total_sum = 0

    for i in range(len(string)):
        curr = string[i]
        if curr == '(' or curr == '[':
            temp *= d[curr]
            continue
        prev = string[i - 1]  # is_valid_form 통해 바르지 않은 input 이미 검증
        if (curr == ')' or curr == ']') and (prev == '(' or prev == '['):
            total_sum += temp
        temp //= d[curr]

    return total_sum

def is_valid_form(string, d):
    # valid 여부 조사할 때 indexError 조심
    stack = []
    for s in string:
        if s not in d:
            return False
        if not stack and (s == ')' or s == ']'):
            return False
        if s == '(' or s == '[':
            stack.append(s)
            continue
        if s == ')' and stack[-1] == '(':
            stack.pop()
            continue
        if s == ']' and stack[-1] == '[':
            stack.pop()
            continue
    if stack:
        return False
    return True


print(solution())

 

 

✅ 2800번 괄호 제거 (G5)

* 처음에 기억할 수 있는 정보가 생각보다 힘이 클 수 있다.

* 가능한 경우의 수의 조합을 정해놓고, 해당 괄호는 무조건 삭제한다고 생각하면 편하다.

2800번: 괄호 제거

# 괄호를 제거해 나올 수 있는 서로 다른 식의 개수를 계산 하자.
from itertools import combinations

def getInput():
    return input()

# 괄호 정보 / 인덱스 기억하기
def get_vps_idx(string):  # [[여는 괄호 인덱스, 닫는 괄호 인덱스], [...], [...], ...]
    stack = []
    result = []
    for i in range(len(string)):
        target = string[i]
        if target != '(' and target != ')':  # 괄호가 아니면 지나감
            continue
        if not stack:
            stack.append([target, i])
        elif target == '(':
            stack.append([target, i])
        elif target == ')' and stack[-1][0] == '(':
            open_bracket = stack.pop()
            result.append([open_bracket[1], i])
    return result

def get_removed_string(target_indices, string):
    result = ''
    open_indices = [i[0] for i in target_indices]
    close_indices = [i[1] for i in target_indices]

    for i in range(len(string)):  # string "(1+(2*(3+4)))"을 돈다.
        curr_str = string[i]
        if curr_str == '(' and i in open_indices:  # 여는 괄호 삭제
            continue
        if curr_str == ')' and i in close_indices:  # 닫는 괄호 삭제
            continue
        result += curr_str
    return result

def solution():
    string = getInput()
    vps_indices = get_vps_idx(string)
    p_cnt = len(vps_indices)

    result = set()  # 괄호가 삭제된 문자열 담을 집합, 중복 제거를 위함
    for target_deleted_cnt in range(1, p_cnt + 1):  # 몇 개 삭제 할지
        combi = list(combinations(vps_indices, target_deleted_cnt))  # 여는 괄호의 인덱스 중에서 조합 선택
        for j in range(len(combi)):
            result.add(get_removed_string(combi[j], string))
    # 결과 프린트
    for s in sorted(result):
        print(s)


solution()

 

 

✅ 2493번 탑 (G5)

2493번: 탑

# 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사
# O(n) 해결

def getInput():
    n = int(input())
    tops = [0] + list(map(int, input().split()))
    return n, tops

def solution():
    n, tops = getInput()
    tops = [[tops[i], i] for i in range(len(tops))]

    stack = []  # [높이, 인덱스]
    result = [0] * (n + 1)

    for i in range(1, n + 1):
        while stack:
            if tops[i][0] > stack[-1][0]:
                stack.pop()
                continue
            result[i] = stack[-1][1]
            break
        stack.append(tops[i])

    for i in range(1, len(result)):
        print(result[i], end=" ")


solution()

 

 

✅ 22942번 데이터 체커 (G4)

* 처음에 기억할 수 있는 정보가 생각보다 힘이 클 수 있다. 22222

* 올바르지 않은 괄호 쌍 문제와 동일하게 해결할 수 있었다.

22942번: 데이터 체커

import sys

def getInput():
    n = int(sys.stdin.readline())

    circles = []  # 각 원의 시작점과 끝점, 원의 식별자를 저장할 리스트
    for circle_num in range(1, n + 1):
        x, r = map(int, sys.stdin.readline().split())
        circles.append([x - r, 'start', circle_num])
        circles.append([x + r, 'end', circle_num])
    return sorted(circles)

def solution():
    circles = getInput()
    stack = []

    for point, point_type, num in circles:
        if not stack:
            stack.append([point, num])
            continue
        if point_type == 'start':  # 현재 점이 시작 점이면 스택에 추가
            stack.append([point, num])
            continue
        if stack.pop()[1] != num:  # 현재 점이 끝 점일 때 스택의 맨 위에 있는 원이 다른 원이면 -> 겹침
            return "NO"
    return "YES"


print(solution())

 

 

✅ 1918번 후위 표기식 (G2)

* infix -> postfix 변환식

1918번: 후위 표기식

def getInput():
    return input()

def solution():
    infix = getInput()

    symbol = {'+': 1, '-': 1, '*': 2, '/': 2}
    stack = []
    postfix = ''

    for s in infix:
        if s.isalpha():
            postfix += s
        elif s in symbol:  # 기호인 경우
            while stack and symbol[s] <= symbol.get(stack[-1], 0):
                postfix += stack.pop()  
            stack.append(s)  
        elif s == '(':  
            stack.append(s)
        elif s == ')':
            while stack and stack[-1] != '(':
                postfix += stack.pop()
            stack.pop()
    while stack:
        postfix += stack.pop()
    return postfix


print(solution())