[백준 1406][C++] 가운데를 말해요

문제 링크

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

1406번: 에디터

---

◆문제 해결 및 설명◆

문제 해설 : 문자열을 커서에 따른 Command로 수정한 결과물을 출력하여라!

 

처음에 문제조건이 0.3초 인걸 봤지만 string으로 짜보았다.(글 하단에 첨부)

바로 시간초과! 알고리즘을 다시 보니 문자열을 삽입과 삭제할 때 걸리는 시간이 가장 길다고 판단되어서 이 부분을 substr로 복사붙여넣기? 로 줄일 수 있나 다시 코드를 짜고 제출했으나 시간초과! 가 발생 했다.

 

알고리즘이 적용되는것은 없었기에 대체할만한 자료구조를 생각하였고 삽입과 삭제가 O(1)을 가지는 연결리스트를 사용하자는 생각이 들었다. 그래서 연결리스트를 통한 구현으로 성공할 수 있었다.

 

다만, 구현하는데 어려움이 있었다. 나는 커서의 위치를 아래와 같이 이터레이터로 구현했다.

    list<char> linkedList;
    list<char>::iterator listCursor = linkedList.end();

 

생각해보니 커서는 Node의 수보다 많았고, 이를 어떻게 처리할지 고민하였다.

예제 입력1 초기 값의 List와 커서

 

따라서 end()가 반환하는 Iterator을 문장의 마지막을 가르키는 커서라고 가정하고 , 삭제 삽입 이동을 구현하였다.

아래는 삭제와 삽입 구현의 그림 예제이다.

 

 

이 문제를 풀면서 Iterator는 배열과 다르게 중간에 값이 삽입, 삭제되더라도 Iterator의 가르키는 값이 바뀌지 않는다는것을 알게 되었다.

그리고 STL 컨테이너가 가지고 있는 Iterator의 증가감산( ++, -- ) 연산자는 STL내에서 오버로딩하여 구현하는 것이므로 자료구조에 맞게 작성됨을 알게 되었다.

 

◆코드 전문◆

#include <iostream>
#include <string>
#include <list>

using namespace std;
template <typename T>
void printLinkedList(const T &linkedList);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string str;
    getline(cin, str);
    int cursor = str.size(), loop;
    cin >> loop;
    cin.get();

    list<char> linkedList;
    for (char ch : str)
    {
        linkedList.push_back(ch);
    }
    list<char>::iterator listCursor = linkedList.end();

    string commandLine;
    while (loop--)
    {
        getline(cin, commandLine);
        switch (commandLine[0])
        {
        case 'L':
            if (listCursor != linkedList.begin())
            {
                listCursor--;
            }
            break;
        case 'D':
            if (listCursor != linkedList.end())
            {
                listCursor++;
            }
            break;
        case 'B':
            if (listCursor != linkedList.begin())
            {
                list<char>::iterator listCursorBuf = listCursor;
                listCursorBuf--;
                linkedList.erase(listCursorBuf);
            }
            break;
        case 'P':
            linkedList.emplace(listCursor, commandLine[2]);
            break;
        default:
            break;
        }
    }
    printLinkedList(linkedList);
}

template <typename T>
void printLinkedList(const T &linkedList)
{
    for (auto listIter : linkedList)
    {
        cout << listIter;
    }
    return;
}

 

 

처음에 제출한 코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    string str;
    getline(cin, str);
    int cursor = str.size();
    int loop;
    cin >> loop;
    cin.get();
    while (loop--)
    {
        string commandLine;
        getline(cin, commandLine);
        switch (commandLine[0])
        {
        case 'L':
            if (cursor > 0)
            {
                cursor--;
            }
            break;
        case 'D':
            if (cursor < str.size())
            {
                cursor++;
            }
            break;
        case 'B':
            if (cursor != 0)
            {
                str.erase(str.begin() + cursor - 1);
                cursor--;
            }
            break;
        case 'P':
            str.insert(str.begin() + cursor, commandLine[2]);
            cursor++;
            break;
        default:
            break;
        }
    }

    cout << str;
}