2021 KAKAO INTERNSHIP [표 편집] [C++]

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

코딩테스트 연습 - 표 편집

---

문제 요약

긴 길이의 배열이 있는 상황이다 

배열의 특정 칸을 가리키는 커서라는 개념이 존재하고 

커맨드 U, D, C, Z에 따라 커서를 이동하거나 , 배열의 특정 칸을 삭제, 복구하는 문제

 

문제 속 요구사항이 명확하다

 

---

나의 풀이

 

이 문제에서 가장 중요한 것은 입력 조건을 정확히 이해해야 한다.

그중에서도 "cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다."

라는 문장이다

 

이 문장을 오인하면 생길 수 있는 상황을 설명하기 전에 구현 방법에는 두 가지가 있다.

1. 실제 배열(연속적인 메모리 공간) 속에서 삭제된 위치 , 복구된 위치 등을 다른 배열을 이용하여 기억하며 모든 커맨드를 수행하는 것
2. 실제 배열이 아닌 포인터가 참조를 이용하여 linked_list를 사용하여 푸는 것

(segment tree와 같은 복잡한 알고리즘을 통해 푸는 방법도 있습니다  공식 해설 )

 

 

1번과 같이 정적인 배열 (연속된 메모리)를 이용하면 생길 수 있는 문제가 있다.

만약  길이가 매우 긴 배열이 존재하고 맨 앞(2)과 맨뒤(10000)에만 유효하고 중간에는 모두 삭제되어있다고 생각해보자

 

      위                                                                                                                                          아래

2

X

X

X

X

X

X

X

X

10000

이 상황 속에서 현재 커서는 2를 가리키고 있다고 할 때 "D 1" 커맨드를 실행하면

구현 1의 상황에서는 어쩔 수 없이 한 칸을 옮기려고 해도 유효한 하나의 칸을 밟을 때까지 계속 내려가기 때문에 10000번에 근사한 실행결과가 생긴다.

 

여기서 아까 처음에 소개한 제약조건을 다시 들고 와서 생각해보면

"cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다."

 

위에 상황 속에서 "D 1" , "U 1"와 같이 한 칸만 내려갔다가 다시 올라오라는 명령을 500,000번 시켜도 제약조건에 위배되지 않는다

하지만 위의 상황에서 입각하여 생각해보면

시간 복잡도는 \( 500000 * 10000 * 2 \) 이기 때문에 시간 초과가 날수밖에 없다

 

 

구현 2 (linked_list)를 활용한 풀이에서는 

실제 가리키는 대상을 삭제해주고 뒤에 다른 노드를 이어줌으로써 시간 초과를 방지할 수 있다.

삭제할 때도 참조에 신경을 쓰면서 구현해야겠지만

  복원할 경우 커서와 멀리 떨어져 있는 공간이라 할지라도 바로 복구 과정이 일어날 수 있게 

앞뒤에 있던 대상을 기억한 상태로 휴지통과 같은 공간으로 보내 주는 식으로 구현해야 한다.

 

연결 리스트를 실제로 구현해본 적이 있다면 어렵진 않은 문제이다.

---

소스코드

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int num;
    Node * next;
    Node * prev; 
};
int get_number(string &str){
    int num=0;
    for(int i=2;i<str.length();i++){
        num*=10;
        num+=(str[i]-'0');
    }
    return num;
}
string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    Node * head = new Node();
    head->prev=nullptr;
    Node * tmp = head;


    for(int i=0;i<n;i++){
        Node * newNode = new Node();
        newNode->num=i;
        tmp->next = newNode;
        newNode->prev = tmp;
        tmp = newNode;
    }

    tmp->next=nullptr;

    stack<Node *> trash;

    Node *cur = head;
    for(int i=0;i<=k;i++){
        cur = cur->next;
    }

    
    for(string str : cmd){
        if(str[0]=='D'){
            int interval = get_number(str);
            while(interval--){
                cur = cur->next;
            }
        }
        if(str[0]=='U'){
            int interval = get_number(str);
            while(interval--){
                cur = cur->prev;
            }

        }
        if(str[0]=='C'){
            
            trash.push(cur);
            if(cur->next==nullptr){
                auto before =  cur->prev;
                before->next=nullptr;

                cur = before;
            }else{

                auto before = cur->prev;
                auto after = cur->next;
                before->next=after;
                after->prev=before;

                cur = after;
            }
            
        }
        if(str[0]=='Z'){
            auto reNode = trash.top();
            trash.pop();
            
            auto before = reNode->prev;
            auto after = before->next;

            if(after!=nullptr){
                before->next = reNode;
                reNode->prev = before;

                after->prev = reNode;
                reNode->next = after;
            }else{
                
                before->next = reNode;
                reNode->prev = before;

                reNode->next=nullptr;
            }
        }

        
    }

    vector<bool> chk(n,false);
    Node *loop = head;

    while(loop->next!=nullptr){
        loop = loop->next;
        chk[loop->num]=true;
    }

    for(int i=0;i<n;i++){
        if(chk[i])
            answer+="O";
        else
            answer+="X";
    }
    return answer;
}