stack

9012. 괄호

괄호
분류: 자료 구조, 문자열, 스택

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

코드

import sys


def stack(valid_ps):
    result = []

    if valid_ps.count("(") != valid_ps.count(")"):
        return "NO"

    for i in valid_ps:
        if i == ")":
            if len(result) == 0:
                return "NO"
            result.pop()
        elif i == "(":
            result.append(")")

    return "YES"


for _ in range(int(sys.stdin.readline())):
    vps = sys.stdin.readline().strip()

    print(stack(vps))

설명

• result를 스택처럼 사용
• 스택에는 ")"만 저장
• 입력받은 문자열의 "("와 ")"의 개수가 같은지 확인
• 문자열의 0번 인덱스부터 반복을 시작, 해당 인덱스값이 "("일 경우 스택에 ")"저장
• 인덱스값이 ")"이지만 스택에 데이터가 없을 경우 "NO"를 반환, 스택에 데이터가 있다면 스택의 마지막 인덱스 데이터를 삭제
• 반복문을 모두 도는 동안 반환이 일어나지 않으면 "YES" 반환

---

3986. 좋은 단어

좋은 단어
분류: 자료 구조, 스택

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.

코드

from collections import deque

cnt = 0
for _ in range(int(input())):
    word = input()
    stack = deque()

    for i in word:
        if len(stack) == 0 or stack[-1] != i:
            stack.append(i)
        else:
            stack.pop()

    if len(stack) == 0:
        cnt += 1

print(cnt)

설명

• deque: 양방향 queue, 스택으로도 사용가능
• 문자열 word의 인덱스값이 스택의 마지막 값과 다르거나 스택이 비어있으면 스택에 저장
• 스택의 마지막 값과 같으면 스택 데이터 삭제
• 반복문을 모두 돌았을 때 스택이 비어 있다면 해당 단어는 좋은 단어로 판별하고 cnt 증가

---

10799. 쇠막대기

쇠막대기
분류: 자료 구조, 스택

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.

코드

import sys
from collections import deque

stack = deque()
bar = 0
razer = True

for s in sys.stdin.readline().rstrip():
    if s == "(":
        stack.append(s)
        razer = True
    else:
        stack.pop()
        if razer:
            bar += len(stack)
            razer = False
        else:
            bar += 1

print(bar)

설명

• 괄호를 사용해 레이저와 막대기를 구분해야 하기 때문에 razer변수 사용
• "("일 경우 막대기인지 레이저인지 모르기 때문에 스택에 저장하고 이후 가장 먼지 나오는 ")"는 레이저를 의미하기 때문에 razer=True로 설정
• ")"일 경우 먼저 스택 데이터를 삭제하고 razer가 True라면 스택에 저장된 "("의 개수가 레이저가 자르는 막대기의 개수이기 때문에 결과값에 더한다.
• ")"인데 razer가 False라면 막대기 1개가 끝났다는 의미로 결과값에 1을 더한다.

---