스택 응용 분석해보기 1편

이전 글에서 스택의 고정 관념을 파쇄를 위해서 글을 쓴다고 했다.  이전글  

먼저 백준의 괄호란 문제를 분석해보자!

9012 괄호 문제

괄호 문자열 Parenthesis String은 (, )로만 구성되어있는 문자열이다. 괄호의 모양이 올바르게 구성된 괄호문자열을 VPS라고 부르고, ( )은 기본 VPS이다.. 예를 들어 (())))() ((())), (() 은 VPS가 아니다.

 선입후출! 먼저 넣고 빼면서 생각하는 방법으로 코딩을 한다면 어떻게 될까? 일단 위 문자열 사진처럼 읽으면서, 스택에 다 넣어두고 뒤에서부터 빼면서 쓴다면 내가 데이터를 읽는 흐름이 보라색 선과 같다.

 이렇게 넣은 상태에서 넣은 값을 하나씩 빼면서 생각한다면 어떻게 생각하게 될까? 어떻게 코드를 짜야할지 감이 잡히지 않는다. 왜???? 왜냐면 넣고 빼면서 읽는 것은 단순하게 뒤에서부터 읽는 것과 마찬가지이기 때문이다.

흔한 고정 관념에 따른 생각 

나는 스택 문제를 풀고 있어!, 그래서 스택을 이용해야해(고정관념에 묶인 중), 그래서 스택에 담긴 값을 뺀 것을 다시 넣어주기 위해서 스택을 하나 더 사용해야겠어!!란 생각을 할 수 있다. 이런 경험이 있다면, 고정관념에 묶인 노예란 증거..

---

스택: 거꾸로 읽기 가능!

스택 없이 거꾸로 읽고 싶다면, 배열과 for문을 이용하여 아래와 같이 코드를 작성해야한다.

스택을 이용한다면?

이로써 스택에 넣고 빼면서 읽는 행위는 거꾸로 읽는 행위란 것을 알 수 있다.

이제 데이터를 원래 흐름대로 읽어보자.

---

우리는 앞에서부터 읽으면서 ( 일 때 스택에 넣고, )일 때 스택에서 뺀다. 모든 데이터를 다 읽은 뒤에 스택에 아무것도 없다면 올바른 괄호 문자열일 것이다.

만약에 )일 때 스택에 (이 없거나, 스택에 (이 남아 있거다면 올바르지 않은 문자열인 것을 알 수 있다.

상대적으로 처음에 배우는 기초 자료구조인 스택은 특별하지 않다. 하지만 익숙하지 않기 때문에 자유자재로 이용하지 못할 뿐! 다음 글에서는 10799 쇠막대기란 문제로 스택을 응용해보려고 한다.