백준 알고리즘 기초강의 2 스택

자료구조 중 스택에 관해 배웠습니다

 

대표적인 문제로 괄호문제 파이프 문제 에디터 문제를 풀었는데

 

핵심 아이디어는 다음과 같습니다

 

괄호문제의 경우

열리는 파이프 닫히는 파이프 갯수가 맞아야하는데 

스택의 푸시팝으로 해결할수있습니다

푸시팝 끝냈을떄 스택에 남아있다면 열린 괄호가 더 많다는 소리고

푸시팝 끝내기 전에 스택이 비어있는 상태에서 팝한다면 닫힌 괄호가 더 많다는 소리입니다

하지만 이 문제는 스택 없이 그냥 카운트를 세서 카운트가 0인지 아닌지로도 파악할 수 있습니다

 

파이프 문제는 초딩 정올 문제였떤걸로 기억하는데

레이저를 쏴서 파이프가 몇개로 나누어지는지 알아맞추는 문제입니다

스택에 인덱스를 넣는데 푸시팝할때 인덱스 차이가 1이라면 () 이런 모양 즉 레이저라는 소리고

이때 팝을 해준담에 스택의 크기만큼 result 에 더해주면 됩니다

팝할때 인덱스 차이가 1이 아니라면 그냥 일반적인 파이프라는 소리이므로 result +=1 을 해주면 됩니다

 

에디터 문제는 배열을 이용하면 삽입 삭제에 o(n)의 시간이 걸리기 떄문에 시간 초과가 나는ㄴ 문제지만

커서를 기준으로 왼쪽 스택 오른쪽 스택으로 나눈다면 삽입 삭제를 모두 o(1)로 처리할 수 있습니다

 

나중에 자바로 한번 풀어보겠습니다!!