[Linked List] 표 편집 - 2021 카카오 채용연계형 인턴십

해결 방법

이 문제는 연결리스트를 이용하여 풀 수 있다. 굳이 포인터를 사용하지 않고도 배열을 이용하여 연결리스트를 구현할 수도 있다. 또, 'Z' 명령은 최근에 삭제했던 행을 복구하는 명령이므로 Stack이 필요하다.

 

주의할 점이 있다면, 맨 앞에 있는 요소는 앞 노드로 연결하는 링크가 없고, 맨 뒤에 있는 요소는 뒷 노드로 연결하는 링크가 없음을 고려해야 한다. 그리고 'U', 'D' 명령의 경우에는 이동할 칸 수를 나타내는 정수가 나오는데, 이 정수는 한 자리 숫자가 아닐 수도 있기 때문에 모든 자리 수를 추출해야 한다.

 

노드를 삭제하는 경우에는 기존 노드의 앞, 뒤 노드를 서로 이어주면 되고, 노드를 복구하는 경우에는 제거되었던 노드의 앞, 뒤 노드를 해당 노드로 이어주면 된다.

 

 

소스 코드

아래 소스 코드의 pre, nxt 배열은 각각 앞, 뒤 노드를 나타낸다.

#include <string>
#include <vector>
#include <stack>
using namespace std;
stack<int> s;

string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    int pre[n];
    int nxt[n];
    for(int i=0;i<n;i++) answer+='O';
    for(int i=0;i<n;i++) {
        pre[i]=i-1;
        nxt[i]=i+1;
    }
    nxt[n-1]=-1;
    for(int i=0;i<cmd.size();i++){
        if(cmd[i][0]=='U') {
            int cnt=stoi(cmd[i].substr(2));
            while(cnt--!=0) k=pre[k]; // 존재하는 행들을 위로 건너뛰기
        }
        else if(cmd[i][0]=='D') {
            int cnt=stoi(cmd[i].substr(2));
            while(cnt--!=0) k=nxt[k]; // 존재하는 행들을 아래로 건너뛰기
        }
        else if(cmd[i][0]=='C') {
            s.push(k);
            if(pre[k]!=-1) nxt[pre[k]]=nxt[k];
            if(nxt[k]!=-1) pre[nxt[k]]=pre[k];
            answer[k]='X';
            if(nxt[k]==-1) k=pre[k]; // 제거되는 행이 마지막 행일 경우
            else k=nxt[k];
        }
        else {
            int t = s.top(); s.pop();
            if(pre[t]!=-1) nxt[pre[t]]=t;
            if(nxt[t]!=-1) pre[nxt[t]]=t;
            answer[t]='O';
        }
    }
    return answer;
}

 

정확성, 효율성 모두 만점