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

※ (링크) 바킹독 유튜브 영상을 통해

학습한 내용을 정리한 것입니다.

 

본인은 JAVA를 활용해 학습하였습니다

비상업적 목적이며, 개인 복습을 위해 업로드한 글임을 다시 한 번 더 이야기드립니다.

 

본문의 모든 내용의 출처는 아래 명시된 링크와 같습니다.

 

 

[목차] 수식의 괄호쌍이란?, 문제 해결을 위한 관찰, 문제 해결 방법, 연습문제

 

[실전 알고리즘] 0x08강 - 스택의 활용(수식의 괄호 쌍)

출처: blog.encrypted.gg/936?category=773649

 

---

수식의 괄호쌍이란?

말 그대로 '수식의 괄호쌍'입니다. 주어진 괄호 문자열이 올바른지 판단하는 문제와 같습니다. 

 

문제 해결을 위한 관찰

문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 것으로 접근합니다.

가장 최근에 것이 먼저 나오는 FIFO입니다.

 

문제 해결 방법

• 여는 괄호를 스택에 추가
• 닫는 괄호일 경우
  • 스택이 비어있으면 올바르지 않는 괄호 ( return False )
  • 스택의 top과 짝이 맞지 않을 경우 올바르지 않는 괄호 ( return False )
  • 스택의 top이 짝과 맞는 괄호일 경우 pop
• 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않으며, 남아있지 않으면 올바른 괄호

---

연습 문제

(1) 백준 4949번 : 균형잡힌 세상

 

 

우와 ㅠㅠ 바킹독 강의 듣기 전, 무작정 문제 풀어보자 하고 했던터라 못 풀어서 결국 다른 분 풀이 보고 이해하고 풀었던 기억이 있는데..ㅠㅠㅠ

 

지금 강의 듣고 이해하고 풀었을 때 시간을 약 3초대에서 약 2초대로 줄였네요 ㅠㅠㅠㅠ 코드는 조금 길어도 ㅋㅋ ㅠㅠ 제가 빨리 생각하고 타이핑하면 되는거니.. 후어어어어ㅓ엉 바킹독 최고 ㅠㅠ ..

 

 

 

---

백준 2504번 꼭 다시 풀기