[Python] 파이썬 스택(Stack) 구현하기

gnwjd309·2022년 5월 18일
0

Python

목록 보기
2/4
post-thumbnail
  • 스택에 대한 기본적인 내용은 여기 참고하기!

스택 사용하기

data_stack = list()

스택은 list를 사용해 구현한다. (큐도 똑같이 list를 사용하여 구현할 수 있지만, queue 모듈이 따로 존재하기 때문에 모르는 사람만 바보다!)

data_stack.append(1)
data_stack.append(2)

print(data_stack)
[1.2]

요소의 추가는 append 함수를 사용한다.

data_stack.pop()
2

list의 pop 함수를 사용하면 가장 마지막에 추가한 요소를 꺼낼 수 있다.

del data_stack[-1]
1

pop함수를 사용하지 않고 마지막 요소를 제거한다면
del 키워드를 사용해 지울 수 있다. 리스트 인덱스에 -를 붙이게 되면 뒤에서부터 시작한다는 의미를 갖는다. 따라서 인덱스 -1은 가장 마지막 요소를 가리키게 된다.


응용하기

백준 알고리즘 9012번

여기에서 문제를 확인하기!


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

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

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

예제 입력1

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(
NO
NO
YES
NO
YES
NO

예제 입력2

3
((
))
())(()
NO
NO
NO

작성한 코드

VPS가 되기 위해서는 문자열이 모두 "()" 형태를 가져야 한다. 즉, "("의 개수와 ")"의 개수가 동일하다는 것을 의미한다.
sum 이라는 변수를 두어, 문자열이 "("일 때는 1씩 더하고 ")"일 때는 1씩 뺀다. 최종적으로 sum이 0이라면, VPS이므로 "YES"를 출력한다.

이때, sum의 값이 같다고 해서 모두 VPS가 아니다. 예를 들어, "))(("라는 문자열을 입력 받는다면 VPS가 아님에도 최종적으로 sum의 값이 0이므로 "YES"를 출력한다. 때문에 sum이 음수일 경우 "NO"를 출력하는 조건을 추가해야 한다. sum이 음수일 경우 ")" 문자가 "("보다 먼저 있다는 것을 의미하기 때문이다.

import sys

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

for i in range(t):
    data = sys.stdin.readline()
    stack = list(data)
    sum = 0

    for j in stack :
        if j == "(":
            sum += 1
        elif j == ')':
            sum -= 1
        
        if sum < 0 :
            print("NO")
            break

    if sum == 0: print('YES')
    else: print('NO')
profile
나 애기 개발자 👶🏻

0개의 댓글