[코테] 스택 stack

YB N·2024년 10월 28일

ADT stack

코딩테스트

목록 보기

4/4

Stack

말 그대로 쌓아 올린다

내가 책더미에 책을 추가하고 싶으면 맨 위에 올리고 = push
원하는 책을 빼고 싶을 때에도 맨 위에서부터 차례로 빼는 = pop

이걸 FILO(Firs In Last Out)이라고 표현 = 선입후출

python에서는 stack을 제공하지 않기 때문에 대안으로 list의 append나 push로 스택을 대체하거나 deque를 응용해서 stack처럼 사용함
그러니까 stack이 실제로 존재하는 자료형은 아님!

하하 그러니까 정리하면
python에는 stack이 없어
그래서 stack을 쓰고 싶으면 네가 구현해야돼
stack은 ADT(Abstract Data Type)으로 실제 자료형으로 있는게 아닌
추상자료형!

Stack의 구현

stack에서는 어떤 연산이 있어야 할까?

push
pop
isFull
isEmpty
top

stack = []
max_size = 10

def push(stack, item):
    if isFull(stack):
        print('stack이 가득 찼습니다')
    else:
        stack.append(item)
    
def pop(stack):
    if isEmpty(stack):
        print('stack이 비어있습니다')
        return None
    else: return stack.pop()
	
def isFull(stack):
    return len(stack) == max_size
def isEmpty(stack):
    return len(stack)==0

더 쉽게쉽게 발전시켜보면?

stack = []

# stack push = list append
# stack pop = list pop

문제 08. 괄호 짝 맞추기

내가 푼 답 :

def solution(strings):
    begin = 0
    end = 0
    for string in strings:
        if string == '(':
            begin += 1
        elif string == ')':
            end += 1
        
        if begin < end:
            return False
        
    if begin == end:
        return True
    else: return False

내가 stack으로 풀려고 노력해서 푼 답:

def solution(strings):
    stack = []
    for string in strings:
        if string == "(":
            stack.append(1)
        else:
            try:
                stack.pop()
            except:
                return False
            
    if len(stack) == 0:
        return True
    else: return False

문제 09. 10진수를 2진수로 변환하기

내가 한 것:

def solution(number):
    # 10 = 2**3 + 2**1
    # 10 = 5*2 = (2*2 + 1) *2
    stack = []
    done = True
    while done:
        if number // 2 == 0:
            done = False
        else:
            stack.append(number % 2)
            number = number // 2
    stack.append(1)
    stack = stack[::-1]
    return stack
    ## list 묶음을 어떻게 string으로 만들지..

내가 한 것 ver2:

def solution(number):
    # 10 = 2**3 + 2**1
    # 10 = 5*2 = (2*2 + 1) *2
    result = ''
    while number // 2 != 0:
        result += str(number % 2)
        number = number // 2
    result += '1'
    result = result[::-1]
    return result

문제 10. 괄호 회전하기

def correct_case(question):
    # small bracket : ()
    # medium bracket : []
    # large bracket : {}
    stack = []
    for candid in question:
        if candid == "(" or "{" or "[":
            stack.append(candid)
        else: 
            if not stack:
                return False
            elif (candid == ")") and (stack[-1] == "("):
                stack.pop()
            elif (candid == "]") and (stack[-1] == "["):
                stack.pop()
            elif (candid == "}") and (stack[-1] == "{"):
                stack.pop()                
            else: return False

    if stack: return False
    else: return True

def rotate_string(string):
    return string[1:]+string[0]

def solution(s):
    result = 0
    for x in range(len(s)):
        if correct_case(s): result += 1
        s = rotate_string(s)
    return result

문제 11. 짝지어 제거하기

내가 쓴 답

def solution(s):
    stack = []
    for alphabet in s:
        if len(stack) == 0:
            stack.append(alphabet)
        elif stack[-1] == alphabet:
            stack.pop()
        else:
            stack.append(alphabet)
    return 1 if len(stack) == 0 else 0

내가 아쉬운 점
True/False boolen을 반납하는 함수의 활용

def solution(s):
    stack = []
    for a in s:
        if stack and stack[-1] == a:
            stack.pop()

        else:
            stack.append(a)
    return int(not stack)

문제 12. 주식 가격

내가 한 것

def solution(prices):
    answer = [0] * len(prices)
    for i in range(len(prices)):
        day = 0
        for future_price in prices[i+1:]:
            if future_price >= prices[i]:
                day+=1
        answer[i] = day
    return answer

시간복잡도가 지금 O(N^2)임
그래서 이 문제의 답이 될 수 없고 stack을 활용하지도 않았음

이렇게 푸는 방식에서 불필요한 연산을 줄여 효율성을 확인해야함

그리고 일단 나 문제 잘못이해함 :> 다시 해보자

문제 13. 크레인 인형 뽑기 게임

내가 한 것

import numpy as np

def solution(board, moves):
    board = np.array(board).T
    result = 0
    stack = [0]
    for move in moves:
        for idx, doll in enumerate(board[move-1]):
            if doll != 0:
                board[move-1][idx] = 0
                if stack[-1] != doll:
                    stack.append(doll)
                else: 
                    stack.pop()
                    result += 1
                break
    return result*2

문제 14. 표 편집

내가 한 것:

def solution(n, k, cmd):
    result = ["X"]*n
    info = list(range(n))
    backup = []

    for command in cmd:
        if command.startswith('U'):
            _, stair = command.split(' ')
            k -= int(stair)
        elif command.startswith('D'):
            _, stair = command.split(' ')
            k += int(stair)
        elif command.startswith('C'):
            backup.append(info.copy())
            candid = info[k] 
            info.remove(candid)
            if k > len(info):
                k = len(info)
        elif command.startswith('Z'):
            info = backup.pop()
        else: print('wrong command')

    for mem in info:
        result[mem] = 'O'

    return ''.join(result)