[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
- 수식의 괄호쌍
- 문제 해결
- Q&A
- 마치며
1. 수식의 괄호쌍
32-{6-(2+4)*7} -> { ( ) } : X
5+{6-(12+4}*7) -> { ( } ) : O
수식의 괄호쌍이란, 주어진 괄호 문자열이 올바른지 판단하는 문제.
2. 문제 해결
1) 문제 해결을 위한 관찰
(())()() : O
))(() : X
()())(() : X
해당 괄호쌍이 맞는지 아닌지 판단하는 '로직'에 대해 생각해보아야 함.
-
가장 보편적인 방법, 안쪽부터 짝맞추기를 해서 지워가는 방법. 짝이 다 맞으면 올바른 괄호쌍, 아니면 틀린 괄호쌍.
-
)의 개수가(개수를 넘지 않으면 됨.
-> 괄호의 종류가 여러가지라면, 괄호의 갯수만으로 판단하기는 부족.
ex)({}) : O, ({)} : X
대신, 붙어있는 (), {}를 지우는 방법은 여전히 동작.
위 방법을 배열로 구현할 경우 최대 N번 중간에 있는 원소의 삭제가 발생하므로 O(N²), 연결 리스트의 경우 O(N).
그러나 스택은 더 간단하게 구현 가능.
따라서 스택으로 구현을 할텐데, 추가로 생각해야 하는 점이 있음.
- 닫는 괄호를, "남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령"이라고 생각해도 됨.
2) 문제 해결 방법
(1) 여는 괄호가 나오면 스택에 추가
(2) 닫는 괄호가 나왔을 경우,
(2.1) 스택이 비어있으면, 올바르지 않은 괄호쌍
(2.2) 스택의 top이 짝이 맞지 않는 괄호일 경우, 올바르지 않은 괄호쌍
(2.3) 스택의 top이 짝이 맞는 괄호일 경우, pop
(3) 모든 과정을 끝낸 후,
(3.1) 스택에 괄호가 남아있으면, 올바르지 않은 괄호쌍
(3.2) 스택에 괄호가 남아있지 않으면, 올바른 괄호쌍
3. Q&A
-
4. 마치며
-
[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
아무것도 모르는 컴공 학생의 Wonder_Land