[C++] 백준 1406번 - 에디터 (스택 풀이 & 연결리스트 풀이)

 

📖 문제

 

 

📋 Stack 풀이 코드

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

int main()
{
    int M;
    string s = "";
    stack<char> left;
    stack<char> right;

    cin >> s;

    for (int i = 0; i < (int)s.size(); i++)
    {
        left.push(s[i]);
    }

    cin >> M;

    for (int i = 0; i < M; i++)
    {
        char cmd, c;
        cin >> cmd;

        if (cmd == 'L')
        {
            if (!left.empty())
            {
                right.push(left.top());
                left.pop();
            }
        }
        else if (cmd == 'D')
        {
            if (!right.empty())
            {
                left.push(right.top());
                right.pop();
            }
        }
        else if (cmd == 'B')
        {
            if (!left.empty())
            {
                left.pop();
            }
        }
        else if (cmd == 'P')
        {
            cin >> c;
            left.push(c);
        }
    }

    // left에 있는 원소들 모두 right로 이동!
    while (!left.empty())
    {
        right.push(left.top());
        left.pop();
    }

    // right에 있는 원소 출력
    while (!right.empty())
    {
        cout << right.top();
        right.pop();
    }
}

👨🏻‍💻 결과

 

📕 풀이 방법

left에는 커서 기준 왼쪽의 원소들, right는 커서 기준 오른쪽의 원소들을 스택으로 저장합니다.

명령들이 끝나면 모든 원소들을 right로 몰아줘서 가장 top의 원소들부터 순서대로 출력을 해줍니다. 

 

 

📋 List 풀이 코드

#include <iostream>
#include <string>
#include <list>
using namespace std;

int main()
{
    int M;
    string s = "";
    string ans = "";

    cin >> s;
    // 연결리스트에 원소 할당
    list<char> li(s.begin(), s.end());

    // 커서위치를 입력된 문자 제일 끝에 위치
    auto cursor = li.end();
    cin >> M;

    for (int i = 0; i < M; i++)
    {
        char cmd, c;
        cin >> cmd;

        if (cmd == 'L')
        {
            if (cursor != li.begin())
                cursor--;
        }
        else if (cmd == 'D')
        {
            if (cursor != li.end())
                cursor++;
        }
        else if (cmd == 'B')
        {
            if (cursor != li.begin()) // 맨 왼쪽이 아니라면
            {
                cursor--;
                cursor = li.erase(cursor); // 삭제
            }
        }
        else if (cmd == 'P')
        {
            cin >> c;
            li.insert(cursor, c); // 문자 c 삽입
        }
    }

    // 연결리스트 출력
    for (cursor = li.begin(); cursor != li.end(); cursor++)
        cout << *cursor;
}

👨🏻‍💻 결과

 

📕 풀이 방법

<list.begin()의 경우 커서 위치>

<list.end()의 경우 커서 위치>

 

- B 커맨드

else if (cmd == 'B')
{
    if (cursor != li.begin()) // 맨 왼쪽이 아니라면
    {
        cursor--;
        cursor = li.erase(cursor); // 삭제
    }
}

명령 'B'의 경우 커서 기준으로 왼쪽 문자를 삭제해야 하므로 cursor를 왼쪽으로 이동 후 erase를 해준 뒤
cursor = list.erase(cursor)로 커서의 위치를 맞춰줍니다.

현재 커서의 위치가 위와 같다고 가정하겠습니다. 그리고 명령어로 'B'가 들어 올 시 커서를 왼쪽으로 이동 후 b 문자를 삭제하겠습니다.

erase 함수의 경우 삭제된 요소의 다음 요소 위치를 반환합니다. 삭제 후 cursor 위치(iterator가 가리키는 위치)에는 현재 빈 공간이므로 cursor는 길을 잃게 됩니다. 그러나 'B' 커맨드 이후 cursor의 오른쪽 문자는 그대로 여야 하므로 cursor를 erase가 반환하는 값으로 맞춰줍니다.

 

- P 커맨드

else if (cmd == 'P')
{
	cin >> c;
	li.insert(cursor, c); // 문자 c 삽입
}

현재 위와 같은 상황에서 문자 'x'를 삽입할 때 현재 커서 기준으로 왼쪽에 문자를 추가해야 합니다.

insert 함수의 경우 현재 커서의 위치에 문자를 삽입하고 기존에 있던 문자는 한 칸 뒤로 밀리게 됩니다.
커서가 문자 'c'를 가리키고 있는 상황에서 문자 'x'를 insert 시 'c'는 뒤로 밀리게 되고
커서의 위치는 그대로 'c'를 가리키고 있기 때문에 따로 커서의 위치를 맞춰주지 않아도 됩니다. 

 

 

 

제가 iterator에 익숙하지 않았어서 꽤나 애를 먹었던 문제였었습니다.
(난이도 실버 III인데 정답률이 26% ;;; 체감 난이도 골드 정도..?)

 

🔗 링크

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

1406번: 에디터