[프로그래머스/C++] 표 편집 (2021 카카오 채용연계형 인턴십)

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 문제 자체가 어렵지는 않은 문제다.

하지만 효율성 테스트가 있기 때문에 문제를 효율적으로 풀기 위한 방법이 필요하다.

 

삭제를 한 칸은 제외하고 이동을 하는게 문제인데, 왜냐하면 삭제한 칸은 제외하고 이동을 해야하기 때문이다.

그렇기 때문에 삭제한 칸이 많다면, 삭제했는지 확인을 하면서 이동을 하기 때문에 효율성이 떨어지게 된다.

 

그렇다면 어떻게 삭제했는지 확인을 줄이면서 효율성을 높일 수 있을까?

 

방법은 여러가지가 있겠지만, 이 문제에서는 U와 D의 총 이동의  횟수가 제한되어 있으므로 삽입과 삭제를 빨리하면 효율성 테스트를 통과할 수 있겠다는 예상을 할 수 있다.

 

그래서 삽입과 삭제를 빨리 할 수 있는 자료구조인 Linked List를 활용해 문제를 풀었다.

 

그리고 되돌리는 연산은 가장 최신의 결과부터 되돌리므로, 후입선출의 구조인 stack을 사용하면 쉽게 문제를 해결할 수 있다.

 

실제로 문제를 풀 때, 처음에는 Linked List를 직접 구현하기 귀찮아서 2차원 vector를 이용해 Linked List와 비슷하게 움직이도록 코드를 구현했다.

 

하지만 효율성 테스트에서 2개를 통과하지 못했고, 결국 Linked List를 직접 구현하기로 했다.

 

Up과 Down이 있으므로 두 방향으로 움직여야하기 때문에 next 노드와 previous 노드를 저장하는 구조로 코드를 구현했고, 내가 실제로 사용할 method들만 구현해 문제를 해결했다.

 

[아이디어 정리]

1. Linked List 자료구조를 이용해 삽입과 삭제 연산을 빠르게 할 수 있도록 한다.
2. 삭제한 행을 되돌리는 연산은 stack을 이용해 가장 최근에 삭제한 결과부터 되돌리도록 했다.
3. 최종적으로 삭제된 행과 삭제되지 않은 행을 return한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;

struct node
{
    int num;
    struct node *nextN;
    struct node *prevN;
};

class LinkedList
{
private:
    node* head;
    node* tail;
public:
    LinkedList()
    {
        head=new node;
        tail=new node;
        head->nextN=tail;
        tail->prevN=head;
    }
    void push_back(int n);
    node* deleteNode(node* nowNode);
    void insertNode(node* nowNode, node* newNode);
    node* GetHead()
    {
        return head->nextN;
    };
    node* GetTail()
    {
        return tail->prevN;
    };
};

void LinkedList::push_back(int n)
{
    node* temp = new node;
    temp->num=n;
    temp->prevN=GetTail(); // 삽입 노드의 앞 노드
    GetTail()->nextN=temp; //이전 노드의 뒷 노드
    temp->nextN=tail; // 삽입 노드의 뒷 노드
    tail->prevN=temp; // 테일 노드의 앞 노드
}


node* LinkedList::deleteNode(node* nowNode)
{
    node* tempP = nowNode->prevN;
    node* tempN = nowNode->nextN;
    tempN->prevN=tempP;
    tempP->nextN=tempN;
    if (tempN==tail)
    {
        return GetTail();
    }
    return tempN;
}


void LinkedList::insertNode(node* nowNode, node* newNode)
{
    node* tempP=newNode->prevN; // 앞에 올 노드
    // node* tempN=nowNode; // 뒤에 올 노드
    
    nowNode->prevN=newNode;
    tempP->nextN=newNode;
}

string solution(int n, int k, vector<string> cmd) {
    string answer = "";
    LinkedList lst; //마지막 위치를 확인하기 위함
    for (int i=0; i<n; i++)
    {
        lst.push_back(i);
    }
    
    node* nowNode=lst.GetHead(); 
    for (int i=0; i<k; i++) 
        nowNode=nowNode->nextN;
    
    stack<pair<node*,node*>> st;
    for (int i=0; i<cmd.size(); i++)
    {
        if (cmd[i]=="C")
        {
            // int ttt=nowNode->num;
            node* tempNNN=nowNode->nextN;
            st.push(make_pair(tempNNN, nowNode));
            nowNode=lst.deleteNode(nowNode);
        }
        else if (cmd[i]=="Z")
        {
            pair<node*, node*> stIdx=st.top(); //first 앞에 second를 삽입
            st.pop();
            lst.insertNode(stIdx.first,stIdx.second);  
        }
        else
        {
            if (cmd[i][0]=='U')
            {
                for (int j=0; j<stoi(cmd[i].substr(2)); j++)
                    nowNode=nowNode->prevN;
            }
            else 
            {
                for (int j=0; j<stoi(cmd[i].substr(2)); j++)
                     nowNode=nowNode->nextN;
            }
        }
    }
    
    node* nowNN=lst.GetHead();
    int a=0;
    while (true)
    {
        if (nowNN==lst.GetTail())
        {            
            for (int i=0; i<nowNN->num-a; i++)
            {
                answer+="X";
            }
            answer+="O";
            for (int i=0; i<n-(nowNN->num+1); i++)
            {
                answer+="X";
            }
            break;
        }
        for (int i=0; i<nowNN->num-a; i++)
        {
            answer+="X";
        }
        answer+="O";
        a=nowNN->num+1;
        nowNN=nowNN->nextN;
    }
    
    return answer;
}

 

---

 

문제는 전혀 어렵지 않은데, Linked List를 구현하는데 엄청난 시간을 썼다.

자꾸 sementation fault (core dumped)오류가 뜨고 몇몇 문제가 실패한다고 에러메세지가 떴다.

하지만 Linked List를 구현하기전 vector로 Linked List를 비슷하게 구현했을 때는 전혀 오류가 없었기 때문에 정신 나갈뻔했다;;

결국 Linked List 앞 뒤에 head와 tail을 추가하고,  "z"연산을 실행하는 부분을 정수에서 node 구조체로 변경하는 등 다양한 시도를 해 겨우 문제를 해결했다...

 

 

프로그래머스