[WEEK 02] 알고리즘 - 스택 문제풀이

10828. 스택

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

기초적인 스택 개념을 이용해 주어진 명령에 따라 실행하는 문제.

import sys

input = sys.stdin.readline

N = int(input())

input_arr = [input().split('\n')[0] for i in range(N)]
stack = []

for str in input_arr:
    if str.split()[0] == 'push':
        stack.append(str.split()[1])
    elif str == 'pop':
        if len(stack) != False:
            print(stack[-1])
            stack.pop()
        else:
            print(-1)
    elif str == 'size':
        print(len(stack))
    elif str == 'empty':
        if len(stack) == False:
            print(1)
        else:
            print(0)
    elif str == 'top':
        if len(stack) != False:
            print(stack[-1])
        else:
            print(-1)

---

10773. 제로

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

import sys

input = sys.stdin.readline

K = int(input())

num_list = [int(input()) for i in range(K)]
stack = []

for num in num_list:
    if num != 0:
        stack.append(num)
    else:
        stack.pop(-1)

print(sum(stack))

---

9012. 괄호

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

주어진 괄호 문자열이 올바른 괄호 문자열(VPS)이기 위해선 다음의 조건들을 만족해야 한다.

문자열은 열린 괄호로 시작하여 닫힌 괄호로 끝나야 한다.
열린 괄호의 개수의 닫힌 괄호의 개수가 같아야 한다.
열리지 않은 괄호가 먼저 닫혀선 안된다.

# 9012. 괄호
# https://www.acmicpc.net/problem/9012

import sys

input = sys.stdin.readline

T = int(input())

str_list = [input().split('\n')[0] for str in range(T)]

for str in str_list:
    num1, num2 = 0, 0
    flag = True
    for char in str:
        if char == '(':
            num1 += 1
        elif char == ')':
            num2 += 1
            if num2 > num1:
                flag = False
                
    if flag == False:
        print('NO')
    else:
        if num1 != num2:
            print('NO')
        else:
            if str.startswith('('):
                if str.endswith(')'):
                    print('YES')

더 좋은 풀이 방법

import sys

input = sys.stdin.readline

T = int(input())

str_list = [input().split('\n')[0] for str in range(T)]

for str in str_list:
    cnt = 0

    for char in str:
        if char == '(':
            cnt += 1
        elif char == ')':
            cnt -= 1
        
        if cnt < 0:
            print("NO")
            break
    
    if cnt == 0:
        print("YES")
    elif cnt > 0:
        print("NO")

스택 개념 이용하여 다시 풀어보기

---

17608. 막대기

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

N개의 막대기가 왼쪽부터 나열되고 오른쪽에서 봤을 때 보이는 막대기의 개수를 구하는 문제.

import sys

input = sys.stdin.readline

N = int(input())
stack = [int(input()) for i in range(N)]

longest = 0
cnt = 0

for stick in stack[::-1]:
    if stick > longest:
        longest = stick
        cnt +=1

print(cnt)

정답 코드를 완성하였지만 마찬가지로 스택의 개념을 적절하게 사용하지 못한 것 같다.