백준 1406번 [에디터](C++)-yes6686- 티스토리

백준 문제 풀이: 1406 [에디터]

---

문제 링크: https://www.acmicpc.net/problem/1406

문제 설명:

초기 문자열에서 커서를 이동하거나 문자 삽입/삭제를 통해 최종 문자열을 만드는 문제입니다. 각 명령은 다음과 같습니다:

• 'L': 커서를 왼쪽으로 이동 (문자열의 시작에선 무시)
• 'D': 커서를 오른쪽으로 이동 (문자열의 끝에선 무시)
• 'B': 커서 왼쪽의 문자 삭제 (문자열이 비어있으면 무시)
• 'P x': 커서 왼쪽에 문자 x 삽입

---

문제 해결 코드

#include <iostream>
#include <stack>
using namespace std;

stack<char> st1; // 왼쪽 커서
stack<char> st2; // 오른쪽 커서

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;

    // 초기 문자열을 스택 st1에 삽입
    for (char c : s) {
        st1.push(c);
    }

    int n;
    cin >> n;

    while (n--) {
        char command;
        cin >> command;

        if (command == 'L') { // 커서를 왼쪽으로 이동
            if (!st1.empty()) {
                st2.push(st1.top());
                st1.pop();
            }
        } else if (command == 'D') { // 커서를 오른쪽으로 이동
            if (!st2.empty()) {
                st1.push(st2.top());
                st2.pop();
            }
        } else if (command == 'B') { // 커서 왼쪽의 문자 삭제
            if (!st1.empty()) {
                st1.pop();
            }
        } else if (command == 'P') { // 커서 왼쪽에 문자 삽입
            char x;
            cin >> x;
            st1.push(x);
        }
    }

    // 결과 출력: 스택을 이용해 최종 문자열 생성
    while (!st1.empty()) {
        st2.push(st1.top());
        st1.pop();
    }

    while (!st2.empty()) {
        cout << st2.top();
        st2.pop();
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 두 개의 스택을 활용해 커서 이동 및 삽입/삭제를 효율적으로 처리합니다.
• 구현 세부사항:
  • 커서의 왼쪽은 스택 st1, 오른쪽은 스택 st2로 관리
  • 'L': st1의 top을 st2로 이동
  • 'D': st2의 top을 st1로 이동
  • 'B': st1에서 pop
  • 'P x': st1에 x 삽입
• 시간 복잡도: O(n + m)
  • 초기 문자열 삽입: O(n)
  • 명령어 처리: O(m)

---

결과

두 개의 스택을 활용해 커서 이동 및 삽입/삭제를 효율적으로 처리하며, 최종 문자열을 생성합니다. 스택 구조를 사용함으로써 최적의 성능을 보장합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!