[바킹독의 실전 알고리즘] 0x08강 - 스택의 활용(수식의 괄호 쌍)
·
Computer Science/자료구조 | 알고리즘
시간 복잡도 배열로 구현 -> 최대 N번 중간에 있는 원소의 삭제 발생 => O(N^2) 연결리스트 -> O(N) => 스택으로 훨씬 간단하게 구현 문자열을 앞에서부터 읽어나갈 때, 닫는 괄호가 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다 문제 해결 방법 여는 괄호 나옴 -> 스택에 추가 닫는 괄호 나옴 스택이 비어 있음 -> 올바르지 X 괄호 쌍 스택의 top이 짝과 맞지 X 괄호 -> 올바르지 X 괄호 쌍 스택의 top이 짝이 맞는 괄호 -> pop 모든 과정을 끝낸 후 스택에 괄호 남아있음 -> 올바르지 X 괄호 쌍 / 남아있지 X -> 올바른 괄호 쌍
