[C++] 백준 1406번 풀이 (에디터)

- 문제 (1406번) : 에디터

• 링크 : https://www.acmicpc.net/problem/1406

• 한 줄로 된 간단한 에디터를 구현하는 문제

  • 에디터가 지원하는 명령어는 4가지이다.

    1. 커서를 왼쪽으로 한 칸 옮기는 명령 ( L )
    2. 커서를 오른쪽으로 한 칸 옮기는 명령 ( D )
    3. 커서 왼쪽에 있는 문자 삭제 ( B )
    4. 입력 받은 $ 위치의 문자를 커서 왼쪽에 추가함. ( P $ )

  • 1. 3. 번 명령어는 커서가 문장의 맨 앞이면 무시
  • 2. 번 명령어는 커서가 문장의 맨 뒤이면 무시

---

- 입력 및 출력

[ 입력 ]

• 첫째 줄에 편집기에 입력되어있는 초기의 문자열 입력
• 둘째 줄에 입력할 명령어의 개수 입력 ( N )
• 셋째 줄부터 N개의 줄에 걸쳐 명령어 입력 ( 문제의 명령어 형태로만 입력)

[ 출력 ]

• 모든 명령어를 수행하고 난 후 편집기에 입력되어있는 문자열 출력

---

- 문제 풀이

• 커서를 기준으로 왼쪽과 오른쪽 상태변화가 일어나는 상황이다.
  그렇기 때문에 커서를 기준으로 왼쪽 공간과 오른쪽 공간을 나눠 관리하면 된다.
• 커서를 기준으로 왼쪽 문자열과 오른쪽 문자열을 각각의 stack으로 관리.
  

• 가장 초기의 문자열은 모두 다 왼쪽 stack에 저장.
• 커서가 왼쪽으로 움직이면 left stack -> right stack 으로 저장
  커서가 오른쪽으로 움직이면 right stack -> left stack 으로 저장
• 커서를 기준으로 왼쪽부분 변경 시 left stack에,
  오른쪽 부분 변경 시 right stack에 영향이 있음.

• 모든 명령어가 전부 수행되고 난 뒤 왼쪽과 오른쪽 stack에 있는 문자열 순서대로 출력.

  • left, right stack에 나눠져있으므로 하나의 stack에 모아 출력.
    ※ stack은 top의 원소가 제일 먼저 pop 되므로 순서 신경써서 합치기.
    
  • 이 예시로 봤을 때 left stack의 원소를 가장 앞 원소부터 출력하고, 그 후 right stack의 원소를 출력하면 된다.
    
    left stack에 있는 문자들은 순서가 반대로 되어있으므로 따로따로 출력하는 것이 아닌 left stack의 문자들을 right stack에 옮겨 top 원소부터 차례로 출력했다.
    

---

- 최종 코드