본문 바로가기

[바킹독 알고리즘] 0x08강:스택의 활용(수식의 괄호 쌍)

@hyeon.s2023. 1. 9. 20:45

수식의 괄호쌍이란?

주어진 괄호, 문자열이 올바른지 아닌지 판단하는 문제이다.

첫번째 예시의 괄호쌍만 본다면 {()} 로 올바른 괄호쌍이지만, 두번째는 {(})로 올바르지 않은 괄호쌍이다.

문제 해결을 위한 관찰

괄호쌍들이 잘 짝을 이루었는지를 판단하려면

" 문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라 생각해도 된다."  (대박 이렇게 생각하면 stack으로 문제를 풀 수 있는거같다.)

문제 해결방법

위 방법을 문제에 활용해 stack에 적용하면 문제를 해결할 수 있다.

결론적으로 stack의 empty() 여부로 올바른 짝인지 아닌지 확인 할 수 있다.!!

문제현황

연습 문제 ✔ 4949 균형잡힌 세상 정답 코드
기본 문제 3986 좋은 단어 정답 코드
기본 문제 9012 괄호 정답 코드
응용 문제 10799 쇠막대기 정답 코드
응용 문제 2504 괄호의 값 정답 코드

 

hyeon.s
@hyeon.s :: 개발로그
목차