스택(stack)구조란? (백준 9012번, 10828번)

스택 구조란, 쌓여 있는(stack) 더미처럼 된 자료구조를 말한다.

 

출처: 무신사

 

그림처럼 쌓은 수건을 위에서부터 사용하면서, 빨래한 새 수건을 다시 위에 쌓으면 아래 있는 수건은 계속 안 써서 먼지가 쌓인다. 이 구조가 스택 구조이다. 스택 구조는 나중에 들어온 데이터가 먼저 나가는 LIFO(Last In, First Out) 구조이다. 또한, 스택에 데이터를 넣는 것을 push, 데이터를 (위에서) 빼는 것을 pop이라고 한다.

출처: GeeksforGeeks

 

백준 9012번: 괄호

 

백준 9012번(괄호)는 스택 문제의 대표적인 유형이다.

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 
여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

 

"("와 ")"로 된 문자열을 받아서, (가 들어올 경우 빈 스택에 push하고, )가 들어올 경우 pop을 시키자. 이때 pop을 시킬 원소가 없으면 VPS가 아닌 문자열이고, 모든 문자에 대해 push와 pop을 마쳤는데 스택의 길이가 0이 아니면 VPS가 아닌 문자열이다. 정상적으로 과정이 종료되며 스택 길이가 0이면 VPS가 맞다. 이를 코드(python)로 아래와 같이 구현했다.

def vps_idenfier(string):
    stack = []
    for parentheses in string:
        if parentheses =="(":
            stack.append(parentheses)
        else:
            if len(stack):
                stack.pop()
            else:
                return "NO"
    if len(stack):
        return "NO"
    else:
        return "YES"

lines = int(input())

for i in range(lines):
    line = input()
    print(vps_idenfier(line))

 

백준 10828번: 스택

 

생각보다 시간 조건이 까다로웠던 문제!!

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
push X: 정수 X를 스택에 넣는 연산이다.pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 스택에 들어있는 정수의 개수를 출력한다.empty: 스택이 비어있으면 1, 아니면 0을 출력한다.top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

 

처음에는 조금 변태같이 구현을 해보았다.

N = int(input())

stack = []

for i in range(N):
    command = input().split()
    try:
        _, num = command
        stack.append(int(num))
    except ValueError:
        command = command[0]
        if command == "pop":
            try:
                print(stack.pop())
            except IndexError:
                print("-1")
        elif command == "size":
            print(len(stack))
        elif command == "empty":
            print(int(not bool(len(stack)))) #음..
        elif command == "top":
            try:
                print(stack[::-1][0])
            except IndexError:
                print("-1")

 

위와 같이 실행한 결과 시간 초과가 걸렸다. Chat GPT에게 물어보니, try-except 구문은 예외가 많이 발생할 경우 시간을 많이 잡아먹을 수 있다고 한다.

 

그래서 try-except를 쓰지 말고 구현해봤다.

N = int(input())

stack = []
for i in range(N):
    command = input().split()
    if command[0] == "push":
        stack.append(int(command[1]))
    elif command[0] == "pop":
        if len(stack):
            print(stack.pop())
        else:
            print("-1")
    elif command[0] == "size":
        print(len(stack))
    elif command[0] == "empty":
        print(int(not bool(len(stack))))
    elif command[0] == "top":
        if len(stack):
            print(stack[::-1][0])
        else:
            print("-1")

 

엥?? 이것도 시간초과가 났다. 두 가지 속도 개선 부분을 수정했다.

1. "top"에서 슬라이싱으로 처리한 stack[::-1][0]은 stack[-1]로 간단하게 바꿀 수 있다. (이건 솔직히 미련한 짓이었다..)
2. sys 내장모듈을 이용하여, input() 함수보다 속도가 빠른 sys.stdin.readline() 을 사용한다.

이 두 가지를 고치자 시간 초과가 해결되었다!!