[프로그래머스] 표편집

string solution(int n, int k, vector<string> cmd){
    vector<int> prev(n), next(n);
    stack<int> removed;
    for(int i=0; i<n; i++){
        prev[i]=i-1; // i번째 요소의 이전 요소 인덱스
        next[i]=i+1; // i번째 요소의 다음 요소 인덱스
    }
    next[n-1]=-1; // 마지막 요소의 다음은 1로 지정 (선형): 마지막 노드의 다음 노드가 없음
    int cur = k;
    
    for(const string&s : cmd){
        char command=s[0];
        int value=0;
        if(s.size() >1) value = stoi(s.substr(2));
        if(command == 'U'){
            while(value--){
                cur=prev[cur];
            }
        } else if(command == 'D'){
            while(value--){
                cur=next[cur];
            }
        } else if(command == 'C'){
            removed.push(cur);
            if(prev[cur]!= -1) next[prev[cur]]=next[cur];
            if(next[cur]!=-1) prev[next[cur]]=prev[cur];
            cur = (next[cur] !=-1)? next[cur]:prev[cur]; // 다음행이 있으면 아래로 없으면 위로
        }
    }
    string answer(n, 'O');
    while(!removed.empty()){
        answer[removed.top()]='X';
        removed.pop();
    }
    return answer;

}

 

[참고]

https://dfdfg42.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%91%9C-%ED%8E%B8%EC%A7%91-Clv3-2021-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EC%B1%84%EC%9A%A9%EC%97%B0%EA%B3%84%ED%98%95-%EC%9D%B8%ED%84%B4%EC%8B%AD

[설명]

1) U X : 현재에서 X칸 위

2) D X : 현재에서 X칸 아래

3) C: 현재 행 삭제 후 바로 아래 행 선택 (마지막이면 마지막의 윗 행)

4) Z: 가장 최근에 삭제된 행을 원래대로 복구

 

변수)

n: 행의 개수, k: 선택된 행의 위치, cmd: 수행한 명령어들이 담긴 문자열 배열

 

[코드]

string answer(n, 'O');

while(!removed.empty()){

answer[removed.top()]='X';

removed.pop();

}

return answer;

 

에서 n개의 answer을 모두 O으로 채움

예를 들어 removed = [4, 2]이면:

removed.top() = 2 → answer[2] = 'X' → "OOXOOOOO"

removed.top() = 4 → answer[4] = 'X' → "OOXOXOOO"