[프로그래머스 level 3] 표편집 (C++)

카카오 2021 인턴

 

 

삽입, 삭제의 시간이 O(1)이거나 O(logn)이면 풀 수 있을 것 같았다. (알고보니 이동시간이 더 중요했다)

log시간을 쓰려면 세그먼트 트리를 써야 할 것 같아서 너무 복잡해질게 예상되어서 그쪽으로는 시도하지 않았다.

예전에 백준에서 풀었던 'AC'문제랑 비슷하다고 생각했다. 그리고 학교 자료구조 시간에 리스트 과제 문제와 비슷했다.

 

처음에 리스트를 사용해 푸는 거라고 생각해서 List STL을 사용해서 시도해 보았다.

STL에 있는 List는 삽입, 삭제는 O(1)이지만, 문제의 'U', 'D', 'Z' 명령어를 처리할 수가 없었다.

 

 

키 포인트

 

Z를 수행하기 위해서는 삭제된 행의 순서를 스택에 입력해 놓아야 한다.

 

C는 리스트에서 값을 지우는 척만 하고 실제로 지워서는 안 된다.

만약 실제로 지워버리면 Z를 수행할 때, 기존 자리를 찾아서 되돌리는데 O(N)만큼의 시간이 걸리기 때문에 효율성에서 out 된다.

 

U와 D를 생각하기 전에 특수 케이스를 생각해 보자.

0 ~ 100001의 숫자가 적힌 배열이 있다.

이때 1 ~ 100000까지의 숫자가 모두 지워지는 데 사용한 명령의 수는 10만 개이다. 그렇다면 남은 명령의 수도 10만개가 될 수 있다.

중간의 모든 숫자를 지웠기 때문에 배열에는 1과 100001 밖에 없다.

이제 U 1 과 D 1 를 통해서 1과 100001을 계속 왕복할 수 있을 것이다.

그런데 C 명령을 통해 값을 지우는 척만 하고 실제로 지우지 않았기 때문에 중간의 배열이 그대로 남아있을 것이다.

그렇다고 1에서 100001을 가는데 중간의 모든 숫자를 건너 갈 수는 없다. 효율성에서 out되기 때문이다.

 

위 케이스가 링크드 리스트가 필요한 이유이다.

링크르 리스트를 사용하면 1의 next는 100001, 100001의 prev는 1 로 설정해서 훨씬 단축된 시간으로 커서를 움직일 수 있게 된다.

 

그래서 아래와 같은 구조체를 사용해서 링크드 리스트를 실제로 구현할 수 있다.

struct Node{
    Node *prev;
    Node *next;
    int num;
};

 

그런데 위 방법으로 구현하는게 기억이 안났던 나는 1차원 배열 2개를 만들어서 풀었다.

i번 행과 연결된 직전 노드를 뜻하는 Prev[i] 배열과

i번 행과 연결된 바로 다음 노드를 뜻하는 Next[i] 배열을 만들었다.

 

https://tech.kakao.com/2021/07/08/2021-%ec%b9%b4%ec%b9%b4%ec%98%a4-%ec%9d%b8%ed%84%b4%ec%8b%ad-for-tech-developers-%ec%bd%94%eb%94%a9-%ed%85%8c%ec%8a%a4%ed%8a%b8-%ed%95%b4%ec%84%a4/

삭제를 할 때 자신의 직전 노드와 다음노드를 이어준다.

**맨 앞 노드와 맨 뒷 노드를 삭제할 때 약간의 주의가 필요하다.

 

되돌리기를 할 때는 꽤나 간단하다.

stack의 특성상 top에 있는 행이 가장 마지막에 수정된 행이다. 그래서 삭제되기 전 자신의 양 옆 노드와 자신을 그대로 이어주면 된다.

(만약 Z 명령이 삭제된 지 가장 오래된 명령을 되돌리는 거라면..?) -> ????

 

 

최종 코드

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

using namespace std;

int Prev[1000001];
int Next[1000001];

string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    
    vector<int> deleted(n, false);
    
    for(int i = 0; i < n; i++){
        Prev[i] = i-1;
        Next[i] = i+1;
    }
    
    vector<int> PrevStack;
    
    for(int i = 0; i < cmd.size(); i++){
        char command = cmd[i][0];
        
        if(command == 'D'){
            int X = stoi(cmd[i].substr(2));
            while(X--){
                k = Next[k];
            }
        }
        else if(command == 'U'){
            int X = stoi(cmd[i].substr(2));
            while(X--){
                k = Prev[k];
            }
        }
        else if(command == 'C'){
            PrevStack.push_back(k);
            deleted[k] = true;
            
            if(Next[k] == n){    // 마지막 부분 삭제
                Next[Prev[k]] = n;
                k = Prev[k];
            }
            else if(Prev[k] == -1){   // 처음 부분 삭제
                Prev[Next[k]] = -1;
                k = Next[k];
            }
            else{
                Next[Prev[k]] = Next[k];
                Prev[Next[k]] = Prev[k];
                k = Next[k];
            }
            
        }
        else if(command == 'Z'){
            int ret = PrevStack.back();
            PrevStack.pop_back();
            deleted[ret] = false;
            
            Next[Prev[ret]] = ret;
            Prev[Next[ret]] = ret; 
        }
    }
    
    for(int i = 0; i < n; i++){
        if(deleted[i]) answer += 'X';
        else answer += 'O';
    }
    
    return answer;
}