2 - 파이썬의 스택을 만나다.

어디서 많이봤던 괄호 문제를 만났다.

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

 

스택 자료구조를 학습할 수 있는 가장 대표적인 예제라고 생각이 되는데, 

자바에서는 Stack 클래스가 존재하여 그것을 사용하면 되었지만

파이썬에서는 이렇게 Stack이라는 것 자체가 있지 않은것 같다.

 

대신 파이썬의 list를 이용하여 스택에 해당하는 기능들을 사용할 수 있는데, 

push는 list의 append()로, 

pop은 pop()으로 (pop은 존재한다.)

peek은 리스트의 [-1]인덱스를 출력하는 것으로 비슷한 기능을 쓸 수 있었다. 파이썬 그것은 대체..

또한 스택이 비었는지 확인하는 것은 length가 0인지 확인하면 되겠다.

 

덱(deque)을 사용한다고도 하는데, 이건 우선 남겨놓자. 들어갈 구석이 없다.

 

그렇다면 예시의 괄호문제를 파이썬으로 해석해보며 스택을 알아보는 시간을 가져보자.

 

 

복잡해보이지만 몇 번 풀어본 사람은 잘 알것이다. 그냥 괄호가 올바르게 '열리고' , '닫혔는지'를 확인하면 되는것이다.

 

1번 데이터 (())()) 

() () () ) 1개가 남는다. -> VPS 아님

 

3번 데이터 (()())((()))

( () () )  ((())) -> 괄호가 모두 닫혀 VPS가 된다

 

뭐 대충 이런식인데, 

 

가장 마지막에 들어간 자료가 가장 먼저 나오는(후입선출, Last In First Out) 스택으로 해결할 수 있는 문제이다. 어떻게 그것이 가능한가?

 

1번 예시를 이용하여 어떻게 VPS가 아닌지 알아보자.

 

VPS가 되려면 여는 괄호 ( 와, 닫는 괄호 ) 가 1:1로 대응되어 짝을 이루어야한다. 

 -> 여는 괄호가 나오면, 반드시 닫는 괄호가 따라와야 한다. 

 -> 여는 괄호만 스택에 집어넣고(push), 만약 닫는 괄호가 나오면 스택에 들어있는 여는 괄호를 제거한다 (pop)

 -> 만약 스택이 비어있는데 닫는 괄호가 나오면 올바르지 않다. VPS가 아님.

 -> 모든 문자열을 거쳐간 후, 스택이 비어있다면 VPS이고, 여는 괄호가 여전히 남아있다면 올바르지 않은 문자열이다.

 

STEP 1. (

스택은 비어있으므로 여는 괄호를 push 한다

STEP 2. )

스택이 비어있지 않으므로,  peek을 사용하여 무엇이 들어있는지 확인해본다. ( 가 들어있으므로 짝을 찾았다. pop으로 들어있는 여는 괄호를 제거한다. 스택은 비어있다. 

STEP 3. 4. 5. 6. 

STEP 1, 2의 반복이다

 

STEP 7. )

이제 이상한 녀석이 등장했다. 스택이 비어있는데 닫는 괄호가 나왔다. 게다가 문자열의 마지막이다.

짝없이 ) 하나만 덜렁 남아있으므로 ()()())는 VPS가 아닌것을 알 수 있다.

 

 

그렇다면 이러한 로직을 작성해보자.

보통 괄호를 확인하는 함수를 하나 만드는듯 한데, 이런 식이다.

 

def is_valid_parentheses(parentheses):
    stack = []
    
    for char in parentheses:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if stack:  # 스택이 비어있지 않은지 확인
                stack.pop()
            else:
                # 스택이 비어있는데 닫는 괄호가 나왔을 경우
                return "NO"
    
    # 모든 괄호를 처리한 후, 스택이 비어있어야 올바른 문자열
    return "YES" if not stack else "NO"

 

이러한 방식을 사용하면 해당 문자열이 잘 닫힌 괄호인지 알 수 있다.

 

고 하는데... 아직 파이썬에 익숙하지 않아서 그런지 직관적으로 이 코드가 어떻다! 라는 느낌이 잘 오지 않는다.

애초에 스택을 이용해 괄호문제를 해결하는 방법은 알고있지만, 함수를 세팅하는 것이나 로직을 설정하는 것이 아직 서툰것 같다.

 

찾아본 자료들은 같은 코드들을 보여준다. 결과적으로 저러한 형태가 가장 좋은 형태이겠지.

로직을 파악했다면, 그것을 코드로 작성해보는 시간이 필요하다.

파이썬의 스택(과 비슷한)기능을 사용하여 스스로 로직을 만들어 보아야겠다. 

 

파이썬은 자바보다야 사용법이 쉬운듯 하지만, 아직 알아야 할 것이 많이 남았다. 다시 만들어보자