[코딩테스트] 스택

스택

- FILO(First In Last Out): 먼저 들어간 데이터가 나중에 나오는 구조

- 함수 호출시 메모리의 스택에 사용

 

ADT

class Stack:
    def __init__(self, size:int = 10):
        self.data = [None for _ in range(size)]
        self.top = -1
        self.size = 10
        
    def isEmpty(self): -> bool
        if self.top == -1:
            return True
        else:
            return False
    
    def isFull(self): -> bool
        if self.top == (self.size - 1):
            return True
        else:
            return False
    
    def push(self, data) -> None:
        if not self.isFull():
            self.top += 1
            self.data[self.top] = data
        return None
        
    def pop(self) -> int|None:
        if not self.isEmpty():
            ret = self.data[self.top]
            self.data[self.top] = None
            self.top -= 1
        return ret

문제 추천

- 괄호 회전하기(Lv2)

- 짝지어 제거하기(Lv2)

- 주식 가격(Lv2)

- 크레인 인형 뽑기 게임(Lv1)

- 표 편집(Lv3)

+)

- 같은 숫자는 싫어(Lv1)

- 올바른 괄호(Lv2)

- 컨트롤 제트(Lv0)

---

괄호 회전하기

 

짝지어 제거하기

def solution(s):
    answer = -1

    stack = []
    for i in s:
        stack.append(i)
        while True:
            if (len(stack) <= 1):
                break
            if (stack[-2] != stack[-1]):
                break
            else:
                stack.pop()
                stack.pop()
        
        
    if len(stack) == 0:
        answer = 1
    else:
        answer = 0
    return answer

주식 가격

def solution(prices):
    answer = []
    for i in range(len(prices)):
        count = 0
        for j in range(i+1, len(prices)):
            if prices[i] <= prices[j]:
                count += 1
            else:
                count += 1
                break
        answer.append(count)
    return answer

크레인 인형 뽑기 게임

 

표 편집

 

같은 숫자는 싫어

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

올바른 괄호

def solution(s):
    answer = False
    
    stack = []
    for i in range(len(s)):
        stack.append(s[i])        
        while True:
            if len(stack) <= 1:
                break
            if stack[-1] == ")":
                if stack[-2] == "(":
                    stack.pop()
                    stack.pop()
            else:
                break

    if len(stack) == 0:
        answer = True
    else:
        answer = False
    return answer

컨트롤 제트

def solution(s):
    answer = 0
    lst = s.split(' ')
    tmp = 0
    for i in lst:
        if i == 'Z':
            answer -= tmp
        else:
            answer += int(i)
            tmp = int(i)
    return answer