8/20 백준

9012

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

스택 기본예제인 괄호검사 문제이다..

• 괄호검사
  • ’(‘을 만나면 stack에 push
  • ’)’을 만났을 때
    • 바로 앞의 괄호는 무조건 ‘(‘여야 한다.
    • stack이 비어있지 않아야 한다.
  • 모든 반복문을 돌고나면 stack은 비어있어야 한다. 그리고 이전의 검사했을 때 부적합하다는 판정이 없어야 한다.

전체 코드

import sys

n = int(sys.stdin.readline())
for _ in range(n) :
    parenthesis = sys.stdin.readline()
    stack = []
    valid = True
    
    for i in parenthesis :
        if (i == '(') :
            stack.append('(')
        elif (i == ')') :
            if (len(stack) == 0 or stack[-1] != '(') :
                valid = False
                break
            stack.pop()

    if (len(stack) == 0 and valid) :
        print("YES")
    else :
        print("NO")
            

1874

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

문제를 이해하는데 한참 걸렸지만 맨밑에 힌트를 잘 읽어보면 이해하기 어렵지 않다. 1부터 n까지의 숫자들을 stack에 push와 pop만 이용해서 입력된 수열을 만드는 문제이다.

• 문제 이해

  예제 입력 1을 예로 들면 4, 3, 6, 8, 7, 5, 2, 1인데, 처음 4는 스택에 1, 2, 3, 4까지 push한 뒤 4를 pop, 3을 pop한다. 4까지 사용했으니까 5, 6을 push, 6을 pop, 7, 8 push, 8을 pop, 나머지 모두 pop하면 된다.

• 변수

  • current : 1 ~ n까지 1씩 올라가면서 입력된 숫자와 비교하는 변수
  • stack : 수열을 만드는데 필요한 stack
  • result : +, -를 저장해 출력할 결과 list
  • possible : 스택으로 해당 입력된 수열을 만들 수 있는지 없는지 판단하는 boolean 변수

• 가능한 action

  1. 숫자를 1 ~ n까지 순차적으로 올라가면서 사용하므로 입력받은 숫자와 같아질 때까지 stack에 숫자를 push한다.
  2. stack의 top과 입력받은 숫자가 같다면 pop해야 한다. current보다 입력받은 숫자가 크지도 않은데 top과 입력이 다르다면 스택으로 불가능한 경우이다(예를 들어 1~6까지 숫자를 사용해 current가 6인데 입력받은 숫자가 4라면 6, 5, 4 순으로 pop을 해야만 하는데 5가 수열에 없으므로 불가능한 경우이다.)

n = int(input())

current = 1
stack = []
result = []
possible = True
for _ in range(n) :
    number = int(input())
    
    while (current <= number) :
        stack.append(current)
        result.append('+')
        current += 1
        
    if (stack[-1] == number) :
        stack.pop()
        result.append('-')
    else :
        possible = False
        break
        
if not possible :
    print("NO")
else :
    for i in result :
        print(i)