[백준 1406] 에디터

[ 백준 1406 : 에디터 ]

스택개념을 안다면 다들 쉽게 풀 수 있는 문제가 몇 가지 있는데
대표적으로 괄호 판단 하는 문제나 사칙연산문제들 그리고 메모장문제가 있다.

내각 메모장 문제라고 하는 문제들은 스택을 두 개 써서 커서를 움직이면서 중간에 글자를 삽입하고 지우고 할 수 있는 문제들이다.
링크드리스트로도 풀 수 있겠지만 0.3초의 짧은 제한시간인만큼 계속해서 커서를 옮기고 최대 글자 수가 60만이기 때문에 무리가 있다.

일단 스택을 두 개(ST1, ST2) 를 쓴다고 가정하면 커서의 위치는 ST1의 사이즈가 된다.

기본 개념은
글자를 단순히 추가할때는 ST1에 푸쉬를 한다. 그리고 커서를 왼쪽으로 옮길때는 ST1의 TOP을 ST2로 푸쉬한다. 그리고 ST1을 POP한다.
또한 커서를 오른쪽으로 옮길때는 반대로 하면되고 해당 커서에서 글자를 삭제할때는 ST1에서 POP하면된다.

그리고 총 문자를 출력할때는 ST1의 인덱스 0부터 ST1.SIZE()까지 ST2.SIZE()-1부터 ST2인덱스0까지 출력하면 된다.

O(N)으로 0.3초안에 들어오니 충분히 풀만하다.

괄호판단 문제나 메모장문제는 다 비슷비슷한 유형이기때문에 한 번 제대로 풀어보면 다음엔 수월하게 풀 수 있다.