[프로그래머스] Level 3. 표 편집

https://school.programmers.co.kr/learn/courses/30/lessons/81303

프로그래머스

 

이걸  풀려고 별 쇼를 다했다. 권장시간이 80분이고, 고난이도라고  체크가 되어있어서 처음엔 80분..? 훗.. 이랬는데 80분도부족했다. 이 문제는 효율성 테스트가 있기 때문에 무식하게 배열 만들어서 하나하나 넣고 빼고하면 안된다. 링크드 리스트의 개념을 가져온다. 대학시절 기억이 새록새록 난다..오젠장..

 

해결방법

 

• 배열 prev, next 를 선언한다. prev는 나의 이전순서 인덱스를 나타낸다. prev[3] 은 3번째아이템보다 앞에 오는 아이템이다. 처음 상태라면 2일것이고, 만약 2번째가 삭제되었다면 1이겠다. next도 마찬가지이다.
• U가 나올 경우, 횟수만큼 깡총깡총 앞으로 가준다. 단순히 -= 해주는게 아니라, 이전아이템>이전아이템 으로 건너간다. D도 마찬가지 방법이다.
• C가 나올 경우, 내 prev가 보는 다음친구는 내가 아니라 내 다음이 된다. 내 next가 보는 이전 친구는 내가 아니라 내 이전이 된다. 그리고 history에 넣어준다.
• Z가 나올 경우, 유령이되었던 나를 복구시킨다. 내 prev 가 보는 다음친구를 나로, 내 next가 보는 이전친구를 나로 복구시켜주고 history에서 제거한다. 

 

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


using namespace std;


string solution(int n, int k, vector<string> cmd) {
    stack<int> history;
    vector<int> prev(n);
    vector<int> next(n);
    for(int i=0;i<n;i++){
        prev[i] = i-1;
        next[i] = i+1;
    }
    
    next[n-1] = -1;
    
    int index = k;
    for(int i=0; i<cmd.size(); i++){
        char command = cmd[i][0];
         
        if(command == 'U'){
          int num = stoi(cmd[i].substr(2));
          for(int jump =0; jump <num; jump++) index = prev[index];  
        }
        else if(command == 'D') {
          int num = stoi(cmd[i].substr(2));
          for(int jump =0; jump <num; jump++) index = next[index];  
        }
        else if(command =='C'){
           
            history.push(index);
            if(next[index] != -1) prev[next[index]] = prev[index]; 
            if(prev[index] != -1)next[prev[index]] = next[index];
            
            if(next[index] == -1) index = prev[index];
            else index = next[index];
            
        }else if(command == 'Z'){
            
            int restore = history.top();
            history.pop();
            if(prev[restore] != -1)next[prev[restore]] = restore;
            if(next[restore] != -1)prev[next[restore]] = restore;
        }
            
    }
    
    string answer(n,'O');

    while(!history.empty()){
        int index = history.top();
        answer[index]= 'X';
        history.pop();
    }
    return answer;
}

마무리하며

테스트 문제에서 "U 3"  처럼 작은 수만 나와있어서  나도모르게 숫자가 10보다 낮을거라고 생각했는지,  substr이 아니라 그냥 cmd[i][2] 를 가져와서 int변환하였다.. 제출하는데 어떤건 성공이고 어떤건 실패하니까 진짜 죽을맛이었다. 나에게 고통을 선사한 문제였다. 너무 알고리즘 자체에 집중해서 디테일을 놓치는 기분이다. 앞으로는 디테일에도 신경을 쓰도록 하자 ㅠㅠㅠ