[코테 재활훈련] 자료구조 별 알고리즘 - Stack

Stack이란?

Stack은 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 LIFO(Last In First Out)형식으로 데이터를 저장하는 자료구조 입니다.
Stack의 top에 데이터를 추가하는 것을 push라고 하고 stack의 top에서 데이터를 추출 하는 것을 pop이라고 합니다.

 

 

List based Stack

Python의 list 자료형을 사용하더라도 push, pop 두 연산 모두 O(1)이기 때문에 Linked list 보다 array list를 활용한 Stack을 구현하는게 편하다

 

 

코테 적용 방법

Stack의 다양한 활용

1. LIFO 특성을 활용한 문제
2. DFS(깊이 우선 탐색)에 사용

코딩 테스트 문제를 접근하는 4가지 단계에 맞춰서 문제를 풀어보자

나의 풀이

LIFO 첫번째 문제

• Step 1 문제 이해하기
  
  • 소,중,대 괄호의 짝이 맞는지 검사해야겠구나
  • input은 String으로 괄호들이 들어오고 output은 Boolean 값을 리턴해주면 되겠구나
• Step 2 접근 방법
  • 한글자씩 스택에 넣다가 괄호가 짝이 맞으면 pop
  • 만약 다 넣고 pop도 다 했는데 남아있으면 유효성 검사 탈락
• Step 3 코드 설계
  
  • python list를 스택으로 선언하자
  • 스택에 한글자씩 push하다가 짝을 만나면 pop하자
  • for문이 끝나고 스택에 아직 남아있는 글자가 있다면 false, 없다면 true
• Step 4 코드 구현

def isValid(self, s: str) -> bool:
    # stack 선언
    stack = []
    # 열림 닫힘 
    open = "({["
    close = {
        ')':'(',
        ']':'[',
        '}':'{',
    }
    # 한글자씩 stack에 push
    for ch in s:
        if len(stack) == 0:
            if ch in close.keys():
                return False
            else:
                stack.append(ch)
        else:
            if ch in open:
                stack.append(ch)
            else:
                if stack[-1] == close[ch]:
                    stack.pop()
                else:
                    return False
    if len(stack) == 0:
        return True
    else:
        return False

 

 모범 답안

• Step 2 접근 방법
  • 여는게 있으면 닫는게 있으니 유효한 경우 글자수는 짝수가 되어야 함
  • 여는게 먼저 와야한다
  • 짝이 맞아야 한다
• Step 3 코드 설계
  • input s의 글자를 for 문을 돌면서 stack에 넣는다
  • 넣을 때 여는 괄호라면 그대로 stack에 넣고
  • 닫는 괄호인 경우에 stack에 짝이 있는지 확인한다.
• Step 4 코드 구현

def isValid(self, s: str) -> bool:
        stack = []
        if len(s)%2 != 0:
            return False
        for ch in s:
            if ch == "(":
                stack.append(")")
            elif ch == "{":
                stack.append("}")
            elif ch == "[":
                stack.append("]")
            elif not stack or stack.pop() != ch:
                return False
        return not stack

 

LIFO 두번째 문제

 

 모범 답안

• Step 2 접근 방법
  • 제약 조건을 통해 O(n^2)로 풀면 안된다는 것을 알 수 있다.
  • Stack에 넣으면서 넣으려는 날씨가 head보다 따뜻하면 pop하면서 경과 일 수를 기록한다
• Step3 코드 설계
  • enumerate함수를 활용하여 (일수, 기온)형태로 바꾼다
  • answer 리스트를 temperature 크기의 0으로 이루어진 리스트로 초기화 한다.
  • while문을 돌면서 조건에 해당하는 경우 해당 인덱스에 맞는 경과 일수로 갱신한다.
• Step4 코드 구현

 

새롭게 알게된 점

• enumerate 내장함수를 사용하면 index를 위한 변수를 따로 선언하지 않고 편하게 사용할 수 있다.
• 주어진 리스트와 같은 크기의 리스트를 결과값으로 리턴해야 할 때 해당 크기만큼 초기화 하자
• 어떤 조건일 때 값을 갱신해 나가는 구조인 경우 Stack을 활용하자