[C++]2021 카카오 채용연계형 인턴십표 편집(프로그래머스 3레벨)

#include <list>
#include <vector>
#include <stack>
#include <string>
using namespace std;
// iter 전체 크기
// iter 삭제시 위치는 남아있다
list<int>::iterator its[1000005] = {};
 
string solution(int n, int k, vector<string> cmd) 
{
    // 들어있는 list
    list<int> listInt = {};
    // 삭제된 stack
    stack<pair<int, int>> stackErased = {};
    // 가리키는 iter
    list<int>::iterator iterCursor = {};
 
    for (int i = 0; i <= n; ++i)
    {
        // 마지막을 알기위해서 n도 입력
        listInt.push_back(i);
    }
 
    auto iter = listInt.begin();
    auto iterEnd = listInt.end();
 
    // its에 listInt를 모두 입력
    for (; iter != iterEnd; ++iter) 
    {
        its[*iter] = iter;
    }
 
    // 현재 커서
    iterCursor = its[k];
 
    for (auto sCmd : cmd) 
    {
        if (sCmd[0] == 'U')
        {
            // 올라가는 크기
            int iNum = stoi(sCmd.substr(2, 6));
 
            while (iNum)
            {
                --iNum;
                --iterCursor;
            }
        }
 
        else if (sCmd[0] == 'D') 
        {
            // 내려가는 크기
            int iNum = stoi(sCmd.substr(2, 6));
 
            while (iNum)
            {
                --iNum;
                ++iterCursor;
            }
        }
 
        else if (sCmd[0] == 'C') 
        {
            // 삭제 시 현재 커서와 커서의 다음을 입력 (나중에 되돌렸을 때를 생각해서)
            stackErased.push({ *iterCursor, *(next(iterCursor)) });
 
            // 현재 커서를 지울 시 다음 커서를 바로 가리키게
            // iter와 listInt둘다 삭제
            iterCursor = listInt.erase(iterCursor);
 
            // 마지막이 커서라면 이전으로 
            if (*iterCursor == n)
                --iterCursor;
        }
 
        else 
        { 
            // 되돌리려면 stack 맨 위에 있는 것을 빼온다.
            pair<int, int> iPair = stackErased.top();
            stackErased.pop();
 
            // iter와 listInt에 다시 넣어놓기
            its[iPair.first] = listInt.insert(its[iPair.second], iPair.first);
        }
    }
 
    string answer(n, 'X');
    for (auto x : listInt)
    {
        if (x != n)
            answer[x] = 'O';
    }
 
    return answer;
}
 

하나하나 O, X로 계산했고 vector도 사용했었는데 위 아래로 이동하는 것에 while 넣고 하다보니 시간초과걸렸다.

linked list를 이용해야하는 문제였다. 효율성 붙은거 보자마자 벡터 버렸어야 했는데...

list 자주 사용하는데 이번엔 바로 사용 못한게 좀 아쉽다