greentea31's Note

https://www.acmicpc.net/problem/1874

풀이 과정

1 ~ n 까지의 수를 스택에 오름차순으로 쌓다가 필요한 수를 stack top에서 뽑아쓸 수 있다.

3, 2, 1은 스택 수열인가? push, push, push, pop, pop, pop을 하면 3, 2, 1이 나오니 스택 수열이다. 그렇다면 3, 1, 2는 스택 수열인가? push, push, push, pop까지는 했는데 stack top에 1이 있으니 2를 꺼낼 수 없으니 스택 수열이 아니다.

1. 현재의 stack top에 있는 수보다 큰 수를 꺼내야 하면 push를 계속 해서 큰 수를 쌓다가 원하는 수가 나오면 pop을 하면 된다.

2. 현재의 stack top과 같은 수를 꺼내야 하면 그냥 pop 한번 해서 수를 꺼내면 된다.

3. 현재의 stack top보다 작은 수를 꺼내야 한다면?

작은 수는 stack top 밑의 어딘가에 깔려있다. stack top을 꺼내지 않고서는 꺼낼 방법이 없다. 따라서 입력받은 수를 스택을 통해 만들면서, 현재의 stack top보다 작은 수를 요구하는 입력이 나온다면 스택 수열로 만들 수 없는 수열이라고 판단하면 된다.

코드

import sys

n = int(input())
stack = [0]
topInput = 0
noCount = False
output = []

for i in range(n):
    inPu = int(sys.stdin.readline())
    if inPu > stack[-1]:
        while inPu > stack[-1]:
            output.append('+')
            topInput += 1
            stack.append(topInput)
        output.append('-')
        del stack[-1]
    elif inPu == stack[-1]:
        output.append('-')
        del stack[-1]
    else: noCount = True

if noCount: print('NO')
else:
    for i in output:
        print(i)

https://www.acmicpc.net/problem/9012

풀이 과정

1. 문자열 도중에 )이 나온 횟수가 (이 나온 횟수보다 많아지면 안된다

2. 문자열이 끝날 때 (이 나온 횟수와 )이 나온 횟수는 같아야 한다

숫자 변수 하나 or 스택을 이용하여 위 조건을 문자열이 만족하는지 검사하면 된다. 스택을 이용하여 검사하려면 (이 나오면 원소를 하나 push, )이 나오면 원소를 하나 pop한다. 스택이 비었는데 pop을 하게 되는 문자열이면 괄호 문자열이 아니고, 문자열을 다 검사했는데 스택에 원소가 남아있으면 괄호 문자열이 아니다. 이외의 경우면 괄호 문자열이게 된다.

코드

import sys

T = int(sys.stdin.readline())

for i in range(T):
    ps = sys.stdin.readline().rstrip()
    stack = []
    noCount = False
    for j in ps:
        if j == '(':
            stack.append(1)
        elif j == ')':
            if len(stack) == 0:
                noCount = True
                break
            else: del stack[-1]

    if len(stack) == 0 and noCount == False: print('YES')
    else: print('NO')