스택. [1406]

[1. 문제 설명]

https://www.acmicpc.net/problem/1406

---

[2. 풀이 접근]

1. 연결 리스트를 이용하여 푸는 방법
   => 반복자를 커서로 사용한다.
2. 스택을 이용한 풀이 방법
   => 여기서는 스택을 이용한 풀이를 정리한다.

구현 컨셉

1. 두 개의 스택을 준비한다.
2. 한쪽 stack (lStack) 의 top 은 커서의 왼쪽 문자를 가리킨다.
3. 반대쪽 stack (rStack) 의 top 은 커서의 오른쪽 문자를 가리킨다.
4. 명령어를 처리한다.
   L: lStack 의 top 을 제거하고, rStack 에 push 한다.
   D: rStack 의 top 을 제거하고, lStack 에 push 한다.
   B: lStack 의 top 을 제거한다.
   P: 새로운 문자를 lStack 에 push 한다.
5. 출력, 재귀롤 이용하여 구현한다.
   => lStack 에 저장 된 값을 먼저 출력하는데, top 이 가장 마지막에 출력되어야 한다.
   => rStack 에 저장 된 값을 그 다음에 출력하는데, top 이 제일 먼저 출력되어야 한다.

시간 초과

• BufferedWriter 의 write 메소드는 문자열, 정수, char 배열을 입력으로 받는다.
• stack 의 저장되는 type 이 Character 인 경우, 출력을 할 때 문자열과 문자 간 결합이 필요하다.
• 문자열의 최대 길이가 600,000 일 때, 이러한 연산이 오버헤드가 될 수 있다.
  => String 과 문자 간 결합 연산이 오버헤드...
• 따라서 stack 에는 문자가 아니라 한 문자를 문자열 형태로 저장하도록 한다.

---

[3. 코드]