문제해결을 위한 관찰
보통 괄호의 쌍을 맞출 때, 제일 안 쪽부터 짝을 찾아서 맞춘다
배열로 구현할 때 O(N^)
연결리스트로 구현할 때 O(N)
하지만 이런 방법은 괄호가 서로 다를 때는 어떻게 할까?
({})
({)}
위 같은 경우에는, 괄호의 짝이 맞지 않다. 그래서 보통 스택을 활용해서 문제를 푼다.
예시
문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각 해도 된다.
밑에가 스택이라고 생각하고, 문자열의 왼쪽부터 괄호들을 담은 후, 닫는 괄호와 짝이 맞다면 스택의 여는 괄호를 없애면 된다. 위 사진은 다 짝이 맞으니 스택은 비어지게 되고 올바른 괄호가 되게 된다.
이번에는 올바르지 않은 괄호 쌍들의 예시이다
올바르지 않은 괄호 쌍들의 예
스택에 여는 괄호부터 담았을 때, 스택의 마지막으로 들어간 괄호인 "{" 와 현재 가르키고 있는 ")" 는 짝이 맞지 않으니 올바르지 않은 괄호라고 볼 수있다.
올바르지 않은 괄호 쌍들의 예 2
이번에는 모든 괄호들의 대해 짝을 맞추고 없애는 작업을 다 했을 때, 스택에 괄호가 남아있다면 이것도 올바르지 않은 괄호 쌍이다.
올바르지 않은 괄호 쌍들의 예 3
마지막으로, 닫는괄호가 나왔을 때 남아있는 괄호가 없으면 올바르지 않은 괄호쌍들이다.
문제 해결 방법
스택의 FIFO 형식이다 제일 먼저 들어 간 괄호가 제일 늦게 나오는 것
- 여는 괄호가 나오면 스택에 추가
- 닫는 괄호가 나왔을 경우,
2-1. 스택이 비어있으면 올바르지 않은 괄호 쌍
2-2. 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍
2-3. 스택의 top이 짝이 맞는 괄호일 경우 pop - 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍, 남아있지 않으면 올바른 괄호 쌍
기록하기