[스택, stack]

stack은 LIFO(Last In, First Out)의 형태를 지닌 자료구조이다.

• PUSH: 새로 들어온 data를 가장 위에 저장한다. O(1)
• POP: 가장 위에 있는(가장 나중에 들어온) data를 제거한다. O(1)
• TOP: 가장 위에 있는 data를 반환한다.
  

C++에서는 STL에 이미 구현되어 있다.

#inclue <stack>
std::stack<int> st;   // int형 stack
std::stack<char> st2; // char형 stack
// using namespace std;를 선언하면 stack<int> st;로 선언 가능

python에서는 stack을 별도로 제공하지 않는다. 대신 list로 stack을 간단히 구현할 수 있다.

push은 list의 append, pop은 list의 pop(), top은 list의 인덱싱을 이용한다.

stack = []  # empty stack
stack.append(1)
stack.append(2)
stack.append(3)  # stack = [1, 2, 3]
stack.append(5)  # stack = [1, 2, 3, 5]
print("The top of the stack is", stack[-1]) # top = 5
print("The size of the stack is", len(stack)) # size = 4
stack.pop()
stack.pop()  # stack = [1, 2, 3]

예제 - 크레인 인형뽑기

그림부터 대놓고 스택이다. 인형을 뽑아서 스택에 넣고, 인형이 사라지면 2개씩 답을 증가하면 된다.

def get_item(board, col):
# board의 col에 해당하는 인형을 뽑는 함수
    N = len(board[0])
    item = 0 # 빈 자리로 초기화
    for row in range(N):
        if board[row][col] != 0:
            item = board[row][col]  
            board[row][col] = 0 # 인형을 뽑은 자리는 빈 자리가 된다
            break
    return item

def solution(board, moves):
    answer = 0
    N = len(board[0])
    stack = [] # empty stack
    for i in moves:
        item = get_item(board, i - 1) # 인형을 뽑는다
        if item != 0:
            if len(stack) != 0 and stack[-1] == item:
                stack.pop()
                answer += 2
            else:
                stack.append(item)
    
    
    return answer

board의 크기가 최대 30x30이므로 get_item은 O(1)이라고 봐도 될 것이다. 만약 board의 크기가 매우 크다면, 반복문으로 찾지 않고 미리 table을 만들어서 인형을 찾으면 된다.