[코딩 테스트 합격자 되기 - 3주차] 스택

스택 개념

선입후출 또는 FILO(First In Last Out) : 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조.

 

스택 정의 

스택은 ADT(abstract data type) - 추상 자료형이며, 인터페이스만 있고 실제로 구현은 되지 않은 자료형

파이썬의 경우, 스택을 제공하지 않지만 대안으로 리스트 메서드인 append() 메서드, push() 메서드로 스택을 대체 가능

deque는 한 쪽으로만 데이터 삽입, 삭제할 수 있는 스택과 다르게 양 쪽에서 데이터를 삽입하거나 삭제할 수 있는 자료구조

이런 특징을 조금만 응용하면 스택처럼 사용할 수 있음.

 

스택 구현하기

stack = []      # 스택 리스트 초기화
max_size = 10   # 스택의 최대 크기

def isFull(stack) :
    # 스택이 가득 찼는지 확인하는 함수
    return len(stack) == max_size

def isEmpty(stack) :
    # 스택이 비어 있는지 확인하는 함수
    return len(stack) == 0

def push(stack, item) :
    # 스택에 데이터를 추가하는 함수
    if isFull(stack) :
        print("스택이 가득 찼습니다.")
    else :
        stack.append(item)
        print("데이터가 추가되었습니다.")

def pop(stack) :
    # 스택에서 데이터를 꺼내는 함수
    if isEmpty(stack) :
        print("스택이 비어 있습니다.")
        return None
    else :
        return stack.pop()

# 스택에 데이터 추가
stack.append(1)
stack.append(2)
stack.append(3)

# 스택에서 데이터 꺼냄
top_element = stack.pop()
next_element = stack.pop()

# 스택의 크기를 구함
stack_size = len(stack)

print("stack",stack)            # stack [1]
print("top_ :", top_element)    # top_ : 3
print("next_ :", next_element)  # next_ : 2
print("size :", stack_size)     # size : 1

몸풀기 문제 - 08. 괄호 짝 맞추기

def solution(s) :
    stack = []                  # 스택 초기화
    for i in range(len(s)) :
        if s[i] == '(' :
            stack.append(s[i])

        else :
            if '(' in stack :   # stack 에 '(' 이 있다면
                stack.pop()
            else :              # stack에 '(' 이 없다면
                return False

    if len(stack) == 0 :        # 쌍이 알맞게 구성되었다면
        return True
    return False                # 아니라면,

s = "(())()"
print(solution(s))  # True

s = "((())()"
print(solution(s))  # False

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

# 10진수를 2진수로 변환하기
def solution(decimal) :
    stack = []
    while decimal > 0 :
        n = decimal % 2     # decimal 을 2로 계속 나누고 그에 대한 나머지 값을 구함
        stack.append(str(n))# 나머지 값을 stack에 추가
        decimal //= 2       # 2로 나눈 decimal 값으로 초기화
    stack.reverse()         
    return ''.join(stack)

de = 10
print(solution(de)) # 1010

de = 27
print(solution(de)) # 11011

de = 12345
print(solution(de)) # 11000000111001
'''
10진수를 2진수로 변환하는 과정을 살펴보면, 
10은 10, 5, 2, 1, 0의 몫을 얻고
나머지는 0, 1, 0, 1 을 얻게 된다. 

이를 뒤집어 읽으면 10에 대한 2진수를(1010)을 얻을 수 있다. 
'''

합격자가 되는 모의 테스트 문제 10. 괄호 회전하기

프로그래머스 - 괄호 회전하기

프로그래머스

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


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

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

s = "[)(]"
print(solution(s))

s = '}}}'
print(solution(s))