#12 스택(Stack) 활용

 스택(Stack)은 데이터를 아래에서 쌓아올리듯 삽입하고 맨 위에서 하나씩 꺼내는 후입선출(LIFO)식 자료구조이다.  매우 단순한 구조를 가지고있지만 OS의 인터럽트나 프로그램에서 함수의 호출 등 이전상태를 보존하고 다음단계를 진행한 뒤 돌아오는 형태의 많은 작업들에 활용되고있으며 그 특성을 이용하여 풀 수 있는 알고리즘 문제들도 있다.  이번에는 스택을 활용한 문제 3개를 정리해본다.

 

1. 균형잡힌 세상(https://www.acmicpc.net/problem/4949)

  소괄호와 대괄호, 영문알파벳, 공백으로 이루어진 문자열이 주어졌을 때, 문자열의 괄호가 모두 정상적으로 쌍을 이루고있는지 확인하는 문제.  괄호쌍을 확인하는 문제는 전형적인 스택 활용 문제중 하나이다.  여는 괄호는 스택에 push하고, 닫는 괄호가 나오면 쌍을 이룰 여는 괄호가 스택에 남아있는지 확인하여 pop 한다. 도중에 닫는 괄호와 쌍을 이룰 여는 괄호가 스택에 남아있지 않거나 모든 작업을 마친 후 여는 괄호가 스택에 남아있다면 괄호쌍이 맞지 않는 문자열임을 알 수 있다.  이 문제를 해결한 코드는 다음과 같다.

 

import sys

input = sys.stdin.read


def sol4949():
    open = {'(', '['}
    close = {')', ']'}
    type = {'(': 0, ')': 0, '[': 1, ']': 1}
    
    def pair_check(s):
        st = []
        for c in s:
        	# 여는 괄호일 경우 스택에 type 값(소괄호, 대괄호 구분)을 push
            if c in open:
                st.append(type[c])
                
            # 닫는 괄호일 경우 스택탑에 같은 타입값이 존재하는지 확인
            elif c in close:
            	# 없을 경우 'no' 반환
                if not st or st[-1] != type[c]:
                    st = [-1]
                    return 'no'
                # 있을 경우 스택 pop
                st.pop()
                
        # 모든 작업 종료 후 스택이 비어있지 않다면 'no' 반환
        if st:
            return 'no'
            
        # 그렇지 않다면 'yes' 반환
        return 'yes'

    return '\n'.join(map(pair_check, input().splitlines()[:-1]))


if __name__ == '__main__':
    print(sol4949())

 

 

 

2. 스택 수열(https://www.acmicpc.net/problem/1874)

  특정 수열을 만들기 위한 스택의 삽입, 삭제 연산 순서를 구하는 문제이다. 간단한 문제지만 스택의 동작을 이해하는데 어느정도 도움이 된다. 이를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.read


def sol1874():
    n, *seq = map(int, input().split())
    i = 1		# 스택에 삽입될 수
    st = []		# 스택
    res = []	# 연산 순서
    
    # 만들어야할 수열을 순회
    for num in seq:
    	# 해당 숫자가 스택에 들어갈 때 까지 push
        while i <= num:
            st.append(i)
            res.append('+')
            i += 1
           
        # 스택 탑의 값이 num과 같지 않다면 'NO' 반환
        if not st or st[-1] != num:
            return 'NO'
            
        # pop
        st.pop()
        res.append('-')
    return '\n'.join(res)


if __name__ == '__main__':
    print(sol1874())

 

 

3. 오큰수(https://www.acmicpc.net/problem/17298)

 주어진 수열의 각 수마다 자신보다 오른쪽에 있으면서 자신보다 큰 수중 가장 왼쪽에 있는 수를 찾는 문제이다.

단순히 자신보다 오른쪽부터 자신보다 큰 값이 나올때까지 선형탐색을 할 경우 O(N^2) 수준의 복잡도를 보이기 때문에 수열의 크기 N이 최대 100만까지 커질 수 있는 이 문제는 해결할 수 없다.  하지만 스택을 활용하면 간단하게 해결 가능한 문제이다.  수열의 수들을 스택에 순차적으로 push하되, push 전에 스택 탑이 자신보다 작은 수가 아닐 때까지 pop한 뒤 자신이 pop한 수의 오큰수가 되도록하면 모든 수의 오큰수를 구할 수 있다. 이 방법으로 문제를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.read


def sol17298():
    n, *seq = map(int, input().split())
    # 오큰수를 찾지 못한경우 -1을 출력해야하기 때문에 디폴트값을 -1로 초기화
    res = [-1] * n
    
    # 수열의 수들을 순회
    st = []
    for i in range(n):
    	# 자신보다 작은 수가 스택 탑인 동안 pop,  pop한 수의 오큰수는 자신이 된다.
        while st and st[-1][0] < seq[i]:
            res[st.pop()[1]] = seq[i]
         
        # 스택에 수열에서의 인덱스와 함께 push
        st.append((seq[i], i))
        
    return ' '.join(map(str, res))


if __name__ == '__main__':
    print(sol17298())

 

 스택은 DFS 등에도 사용 가능한 자료구조이지만 이런 경우 보통 실제로 스택을 사용하기보다는 함수의 재귀호출 형태로 구현하게 되기 때문에 그부분은 따로 다루지 않기로한다.