스택

• 파이썬은 기본적으로 스택 자료구조를 제공하지 않지만, 리스트를 이용해 스택을 구현할 수 있다.
• 스택은 LIFO(Last In, First Out) 방식으로 동작하며, 마지막에 추가된 항목이 가장 먼저 제거되는 구조
• 파이썬 리스트의 몇 가지 메서드를 사용하면 스택의 기본 연산을 구현할 수 있다.

 

1.스택 연산

• push: 스택에 데이터를 추가하는 연산

stack = []
stack.append(10)  # 스택에 10 추가
stack.append(20)  # 스택에 20 추가
print(stack)  # 출력: [10, 20]

 

• pop: 스택에서 가장 마지막에 추가된 데이터를 제거하고 반환하는 연산

popped_element = stack.pop()  # 스택에서 가장 위에 있는 20을 제거하고 반환
print(popped_element)  # 출력: 20
print(stack)  # 출력: [10]

 

• isFull: 스택이 가득 찼는지 확인하는 연산 (파이썬 리스트는 동적으로 크기가 늘어나므로 따로 구현하지 않음)

max_size = 10
def isFull(stack):
    return len(stack) == max_size

print(isEmpty(stack))  # 출력: False (스택에 10이 있음)

 

• isEmpty: 스택이 비어 있는지 확인하는 연산

def isEmpty(stack):
    return len(stack) == 0

print(isEmpty(stack))  # 출력: False (스택에 10이 있음)

 

• top (peek): 스택의 가장 위에 있는 데이터를 반환하되, 제거하지 않음

def top(stack):
    if isEmpty(stack):
        return None
    return stack[-1]

print(top(stack))  # 출력: 10 (스택의 맨 위 요소)

코테에서 괄호 문제 나오면 스택 생각!

짝을 짓는다 나오면 스택 생각!

이들 모두 가장 최근에 탐색한 데이터를 비교하는 원리 -> 스택

 

문제

'''
s=(())() return True
s=((())() return False
'''

def solution(s):
    stack=[]
    for i in s:
        if i =='(':
            stack.append(i)
        elif i ==')':
            if stack:
                stack.pop()
            else:
                return False
    if stack:
        return False
    else:
        return True
print(solution("(())()"))
print(solution("((())()"))

 

'''
10진수 -> 2진수
decimal: 10, 반환값: 1010
decimal: 27, 반환값: 11011
decimal: 12345, 반환값: 11000000111001
'''

def solution(decimal):
    stack=[]
    while decimal>=1:
        na = decimal%2
        decimal = decimal//2
        stack.append(str(na))
    return ''.join(stack[::-1])

print(solution(10))
print(solution(27))
print(solution(12345))

 

https://school.programmers.co.kr/learn/courses/30/lessons/76502

이 문제에서 이 부분 생각하는게 힘들었다.

회전시킨 배열을 생각해보자

  n = len(s)
  for i in range(n):
    stack = [ ]
    for j in range(n):
      c = s[(i + j) % n]

 

'''
s= "[](){}" result =3
'''



def solution(s):
    answer=0
    n = len(s)
    for i in range(n):
        stack = []
        for j in range(n):
            c= s[(i+j) %n]
            if c=="(" or c=="[" or c =="{":
                stack.append(c)
            else:
                if not stack:
                    break
                if c ==")" and stack[-1] == "(":
                    stack.pop()
                elif c =="}" and stack[-1] == "{":
                    stack.pop()
                elif c =="]" and stack[-1] == "[":
                    stack.pop()
                else:
                    break
        else:
            if not stack:
                answer += 1
    return answer

print(solution("[](){}"))

스택문제에서 많이 실수하는 부분: 스택이 비었는지 체크해야 한다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/12973

'''
s="baabaa" result = 1
s="cdcd" result = 0
'''



def solution(s):
    stack=[]
    for c in s:
        if not stack: #stack이 비었으면
            stack.append(c)
        else: #stack에 비어있지 않다면
            if stack[-1] == c: #가장 마지막값과 비교해서 같다면, 마지막값 삭제
                stack.pop()
            else: #다르면, c도 스택에 추가
                stack.append(c)
    if not stack:
        return 1
    else:
        return 0


print(solution("cdcd"))

 

https://school.programmers.co.kr/learn/courses/30/lessons/42584

'''
prices=[1, 2, 3, 2, 3]
return = [4, 3, 1, 1, 0]
'''



def solution(prices):
    arr=[]
    for i in range(len(prices)):
        time=0
        for j in range(i+1,len(prices)):
            time+=1
            if prices[i]>prices[j]:
                break
        arr.append(time)
    return arr

print(solution([1, 2, 3, 2, 3]))

 

https://school.programmers.co.kr/learn/courses/30/lessons/64061

'''
board = [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]]
moves = [1,5,3,5,1,2,1,4]
result = 4
[0,0,0,0,0],
[0,0,1,0,3],
[0,2,5,0,1],
[4,2,4,4,2],
[3,5,1,3,1]
'''


def solution(board, moves):
    cnt = 0
    stack=[]


    # for i in moves:
    #     if i==1:
    #         #board의 1번째열 중 가장 행이 낮은 0이 아닌 값을 0으로 바꾸고, 해당 값을 stack에 추가
    #     elif i == 2:
    #         #board의 2번째열 중 가장 행이 낮은 0이 아닌 값을 0으로 바꾸고, 해당 값을 stack에 추가
    #     elif i == 3:
    #         #board의 3번째열 중 가장 행이 낮은 0이 아닌 값을 0으로 바꾸고, 해당 값을 stack에 추가
    #     elif i == 4:
    #         #board의 4번째열 중 가장 행이 낮은 0이 아닌 값을 0으로 바꾸고, 해당 값을 stack에 추가
    #     elif i == 5:
    #         #board의 5번째열 중 가장 행이 낮은 0이 아닌 값을 0으로 바꾸고, 해당 값을 stack에 추가
    # #stack에 -> [4,3,1,1,3,2,4] 남게 되고,
    # stack=[4,3,1,1,3,2,4]
    
    for move in moves:
        col = move - 1  # moves는 1-based, 파이썬은 0-based이므로 -1
        for row in range(len(board)):  # 해당 열에서 가장 위에 있는 인형을 찾는 루프
            if board[row][col] != 0:  # 0이 아닌 값을 찾으면 그 인형을 뽑음
                stack.append(board[row][col])  # 인형을 뽑음
                board[row][col] = 0  # 해당 자리를 0으로 바꿈 (인형 뽑음)
                break


    i = 0
    cnt = 0
    while i < len(stack) - 1:  # i가 마지막 인덱스보다 작을 때까지만 반복
        j = i + 1
        if stack[i] == stack[j]:
            stack.pop(j)  # j번째 값을 먼저 제거
            stack.pop(i)  # i번째 값을 제거
            cnt += 1
            # i와 j를 다시 0으로 설정하여 처음부터 다시 검사
            i = 0
        else:
            i += 1  # 값이 다르면 다음으로 이동
    return cnt*2

# 순서대로 4, 4, 0 나와야 한다.
print(solution([[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]], [1,5,3,5,1,2,1,4]))
print(solution([[1, 0, 0, 0, 0], [2, 0, 0, 0, 0], [2, 0, 0, 0, 0], [1, 0, 0, 0, 0], [3, 0, 0, 0, 0]], [1, 1, 1, 1]))
print(solution( [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]], [1, 2, 3, 4, 5]))