스택의 활용(백준 9012,4949)

마침 스택을 보고 와서인지 문제를 보자마자 스택이 떠올랐다.

1. 스택이 비었다면 입력값을 추가한다.

2. 입력값과 스택의 마지막값이 같다면, 스택에 입력값을 추가한다.

3. 또한 스택의 마지막값이 )이고, 입력값이 (일때도 추가한다.

4. 스택에 남아있는 것이 없다면 YES, 남아있다면 NO를 출력하게 한다.

 

n=int(input())
for _ in range(n):
    stack=[]
    inp=list(input())
    for x in inp:
        if not stack:
            stack.append(x)
        else:
            pop=stack.pop()
            if pop==x or (pop==")" and x=="("):
                stack.append(pop)
                stack.append(x)
    if not stack:
        print("YES")
    else:
        print("NO")

처음에 ),(의 예외처리를 안해줘서 한번 틀렸다.

 

 

4949 역시 동일하게 스택을 이용한 문제다.

하지만 이건 좀더 심화버전이다.

다른 문제는 무시하고 (,),[,]일때만 고려해서 코드를 짜주면 되겠다.

while 1:
    stack=[]
    inp=list(input())
    if inp[0]==".":
        break
    for x in inp:
        if x=="(" or x=="[" or x=="]" or x==")":
            if not stack:
                stack.append(x)
            else:
                pop=stack.pop()
                if pop=="(" and x!=")":
                    stack.append(pop)
                    stack.append(x)
                elif pop=="[" and x!="]" :
                    stack.append(pop)
                    stack.append(x)
                elif pop=="]":
                    stack.append(pop)
                    stack.append(x)
                elif pop==")":
                    stack.append(pop)
                    stack.append(x)
    if not stack:
        print("yes")
    else:
        print("no")

동일한 알고리즘이므로 자세한 설명은 생략하겠다.