[백준] 1406 에디터

문제 설명

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

1406번: 에디터

초기에 편집기에 있는 문자열이 주어지고, 명령어가 주어지면 해당 명령어에 맞게 수행 한 후의 문자열을 구하기

 

문제 풀이법

처음에는 vector로 풀었다

예제에 있는 답은 맞았지만 5% 즈음부터 시간초과로 실패하고 말았다

 

vector가 아닌 list로 풀어야 시간초과가 안난다고 한다

그 이유는 vector는 연속적인 배열이기에 중간에 요소가 하나 제거된다면, 당겨야 하는 상황이 발생한다고 한다

따라서 맨 앞과 끝을 제외한 삽입/제거는 느리다고 한다

 

반면에 list는 doubly linked list로 구현되어 있기에, 어느 위치에서도 삽입 제거가 빠르다고 한다

 

처음에 string을 입력 받고 list에 넣어주는 작업을 한다

이때 커서는 맨 뒤의 요소로 정한다

 

총 n번 반복하면서 명령어를 처리해준다

•  L 
  • 커서가 맨 앞의 요소인지 확인 후, 아니라면 cur-- 해준다
• D
  • 커서가 맨 뒤의 요소인지 확인 후, 아니라면 cur++ 해준다
• B
  • 커서가 맨 앞의 요소인지 확인 후, cur--해준 후 그 값을 erase한다 
• P $
  • P가 들어오면 문자 하나를 입력 받은 후 insert한다

 

소스 코드

#include <iostream>
#include <list>

using namespace std;

int main()
{
    string str;
    int n;
    
    getline(cin, str);
    cin >> n;
    
    list<char> l;
    
    for (int i = 0; i < str.size(); i++)
        l.push_back(str[i]);
        
    auto cur = l.end();
    
    for (int i = 0; i < n; i++)
    {
        char c;
        cin >> c;
        
        if (c == 'L')
        {
            if (cur != l.begin())
                cur--;
        }
        
        else if (c == 'D')
        {
            if (cur != l.end())
                cur++;
        }
        
        else if (c == 'B')
        {
            if (cur != l.begin())
                cur = l.erase(--cur);
        }
        
        else if (c == 'P')
        {
            char tmp;
            cin >> tmp;
            l.insert(cur, tmp);
        }
    }
    
    for (auto i : l)
        printf("%c",i);
    
    
    
    return 0;
}

 

 

vector를 사용해서 풀었지만 시간초과가 난 풀이

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    string str;
    int n;
    int cur = 0;
    
    getline(cin, str);
    cin >> n;
    
    vector<char> v;
    
    while (str[cur])
    {
        v.push_back(str[cur]);
        cur++;
    }
    
    for (int i = 0; i < n; i++)
    {
        char c;
        
        cin >> c;
        
        if (c == 'L')
        {
            if (cur != 0)
                cur--;
        }
        else if (c == 'D')
        {
            if (cur != v.size())
                cur++;
        }
        else if (c == 'B')
        {
            if (cur != 0)
            {
                v.erase(v.begin() + cur - 1);
                cur--;
            }
        }
        else if (c == 'P')
        {
            char tmp;
            
            cin >> tmp;
            v.insert(v.begin() + cur, tmp);
            cur++;
        }
    }
    
    for (int i = 0; i < v.size(); i++)
    {
        printf("%c",v[i]);
    }
    
    
    return 0;
}