백준 1406 에디터 C++

백준 에디터 1406 C++

문제 설명

문제

한 줄로 된 문자열과 입력 명령들이 주어진다. 커서는 문자의 사이(맨 앞과 맨 뒤 포함)에 위치할 수 있다. 아래의 명령어를 수행하는 프로그램을 작성하시오.

• L : 커서를 왼쪽으로 한 칸 옮김 (커서가 맨 앞이면 무시됨)
• D : 커서를 오른쪽으로 한 칸 옮김 (커서가 맨 뒤이면 무시됨)
• B : 커서 왼쪽에 있는 문자를 삭제함 (커서가 맨 앞이면 무시됨)
• P $ : $라는 문자를 커서 왼쪽에 추가함

---

테스트케이스

abcd
3
P x
L
P y

---

문제 작동원리

초기 상태 (문자열 abcd, 커서는 맨 뒤에 위치)

a b c d _

• 문자열이 abcd이고, _는 커서를 의미합니다.
• 입력 직후에는 항상 커서가 문자열 맨 끝에 있습니다.

---

(1) P x 실행

• 명령어 P는 문자를 커서 왼쪽에 삽입합니다.
• 현재 커서는 맨 뒤(_)에 있으므로, `'x'`가 `'d'` 뒤에 삽입됩니다.

a b c d x_

• 따라서 문자열은 `"abcdx"`가 되고, 커서는 여전히 `'x'` 뒤에 있습니다.

---

(2) L 실행

• 명령어 L은 커서를 왼쪽으로 한 칸 이동시킵니다.
• 원래 커서는 `'x'` 뒤에 있었는데, 한 칸 왼쪽으로 이동하면서 `'x'`의 앞, 즉 `'d'`와 `'x'` 사이로 이동합니다.

a b c d _ x

• 이제 커서는 `'d'`와 `'x'` 사이에 있습니다.

---

(3) P y 실행

• 명령어 P는 문자를 커서 왼쪽에 삽입합니다.
• 현재 커서는 `'d'`와 `'x'` 사이에 있으므로, `'y'`가 그 위치에 삽입됩니다.

a b c d y_ x

• 따라서 최종 문자열은 `"abcdyx"`가 됩니다.

---

문제풀이 아이디어

이 문제는 문자열 편집기를 구현하는 시뮬레이션 문제입니다. 문자열의 중간 삽입, 삭제, 커서 이동을 빠르게 처리해야 하므로 연결리스트(list 컨테이너)를 사용하는 것이 적합합니다.

• list<char>를 사용하면 삽입과 삭제가 O(1) 시간에 가능합니다.
• iterator를 사용하여 커서를 표현합니다.
• 커서의 이동은 lt++, lt--로 처리합니다.
• erase와 insert는 반복자가 가리키는 위치를 기준으로 처리됩니다.
• erase(--lt)로 커서 왼쪽 문자를 삭제하고, 반환되는 반복자로 커서를 갱신합니다.

---

전체코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <list>
using namespace std;
int main(void)
{
    int N;
    char arr[100001], k;
    cin >> arr;
    cin >> N;
    list<char> st;
    for (int i = 0; arr[i] != '\0'; i++)
    {
        st.push_back(arr[i]);
    }
    list<char>::iterator lt = st.end();
    for (int i = 0; i < N; i++)
    {
        cin >> k;
        if (k == 'L' && lt != st.begin())
            lt--;
        else if (k == 'D' && lt != st.end())
            lt++;
        else if (k == 'B' && lt != st.begin())
        {
            lt = st.erase(--lt);
        }
        else if (k == 'P')
        {
            char ch;
            cin >> ch;
            st.insert(lt, ch);
        }
    }
    for (list<char>::iterator i = st.begin(); i != st.end(); i++)
        cout << *i;
    cout << endl;
    return 0;
}

---

개별코드

1. 초기 문자열 입력 및 리스트 생성

for(int i=0;arr[i]!='\0';i++)
{
    st.push_back(arr[i]);
}
list<char>::iterator lt=st.end();

• 입력받은 문자열을 list<char>에 삽입합니다.
• 커서(lt)는 문자열 맨 끝에서 시작합니다.

---

2. 명령어 처리

if(k=='L' && lt!=st.begin())
    lt--;

• L: 커서를 왼쪽으로 이동.

else if(k=='D' && lt!=st.end())
    lt++;

• D: 커서를 오른쪽으로 이동.

else if(k=='B' && lt!=st.begin())
{
    lt=st.erase(--lt);
}

• B: 커서 왼쪽 문자를 삭제. --lt로 왼쪽으로 한 칸 이동 후 erase.
• erase는 삭제된 위치 다음을 가리키는 반복자를 반환하므로 lt를 갱신합니다.

else if(k=='P')
{
    char ch;
    cin>>ch;
    st.insert(lt,ch);
}

• P: 입력받은 문자를 커서 왼쪽에 삽입.

---

3. 최종 출력

for(list<char>::iterator i=st.begin();i!=st.end();i++ )
    cout<<*i;

• 리스트 전체를 순회하며 최종 문자열을 출력합니다.

---

결론

이 문제의 핵심은 문자열 중간 삽입·삭제를 효율적으로 처리하기 위해 연결 리스트(list)를 활용하고, 반복자(iterator)를 커서처럼 사용하는 점입니다.

• list<char>는 삽입/삭제가 O(1)이라 빠릅니다.
• iterator lt를 커서로 두어 위치를 쉽게 이동할 수 있습니다.
• erase와 insert의 반환값을 적절히 활용해야 커서 무효화 문제가 발생하지 않습니다.

👉 결국 이 문제는 리스트(list)와 반복자(iterator)의 기본 동작을 이해하는 것이 핵심입니다.