Programmers - 표 편집

---

title: Programmers - 표 편집
date: 2022-10-17
tags:

• Algorithm

---

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

문제 요약

표의 크기와 현재 위치가 주어지며, 주어진 명령을 수행한다.
각 명령의 수행은 문제를 직접 확인하는 것이 빠르다.
주어진 명령을 전부 수행했을 때, 그대로 남아있는 row는 O, 삭제된 row는 X로 문자열을 구성하여 return한다.

문제 풀이

표의 순서가 정해져 있으며, 비어있는 row는 탐색하지 않는 조건 등이 존재하는 문제이다.
적절한 자료구조를 이용하여 표를 구성하는 문제임을 바로 파악할 수 있었다.
처음에는 vector를 이용하였지만, 예상대로 탐색 속도는 빠르더라도 삽입 및 삭제의 overhead가 너무 커 효율성 테스트에서 TLE가 발생하였다.
결국 귀찮은 방법이지만 Double LinkedList를 구현하여 문제를 해결하였다.
List Container를 이용하는 것도 하나의 방법이나, 어떠한 문제가 있다고 판단하여 List를 사용하지 않았다.

글을 쓰면서 무슨 문제가 있다고 판단하였는지 찾아보았으나, 짧은 시간을 내어 며칠동안 풀었기에 기억이 나지 않는다.
insert와 erase는 쉬우며, iterator를 이용하면 앞뒤 탐색도 가능하다. 왜 안 썼는지 모르겠다.

[ Data ] -> [ Data ] 처럼 빈 Node를 맨 앞,뒤에 배치하여 Root와 Tail로 쓸 수 있다.
하지만 이 경우 복구하는 Z 명령에서 Root보다 앞에 있는 Node를 복구하면 잘못된 순서로 복구가 되는 문제가 발생한다.
이 문제 때문에 Root -> [ Data ] -> ... 방식으로 Root Node를 배치하였다.
위, 아래 순회는 pNext와 pPrev로 이동한다.
삭제하는 C 명령의 경우 현재 Node의 앞뒤를 이어주고, Node 통째로 stack에 넣는다.
복구하는 Z 명령의 경우 stack에서 바로 빼주며, 해당 Node의 앞뒤에 있던 Node가 해당 Node를 가리키는 작업을 해준다.
평범한 표라면 이러한 방식으로 구현하면 순서가 꼬이거나 삭제된 Node를 가리키는 문제가 발생한다.
하지만 이 문제에서 제시된 표는 복구가 가장 최근에 삭제한 Node부터 복구가 된다.
현재 Node의 앞뒤중 하나라도 삭제된 Node가 존재하면 그 Node가 더 나중에 삭제되었기에 그 Node가 먼저 복구되어야 한다.
이러한 특성이 존재하기에 Node를 통째로 stack에 넣었다가 빼서 처리를 해도 문제가 없는 것이다.


카카오의 문제이므로 현실의 문제에 적용해보았으며, 하나가 아닌 두 개의 문제로 분리할 수 있었다.
우선 표에는 순서가 존재하며, 이를 하나씩 탐색한다. 삽입 및 삭제가 빈번할 경우, 연속적인 데이터를 유지하는 것에 많은 overhead가 발생한다.
Logical Address를 사용하는 것이 나으며, 이 경우 순서대로 탐색하려면 Linked List 혹은 Hash를 이용한 접근을 진행해야 한다.
Hash를 이용할 경우, index를 다시 정렬할 경우 O(n)의 index 수정 시간이 소모된다. 데이터를 통째로 옮기는 것은 아니지만, 순서를 유지하기 위해 이러한 작업이 필요해진다.
혹은 index를 그대로 유지한다. 이 경우 Hash 값의 value를 NULL, 혹은 특정 값으로 바꾸어 불필요한 Disk I/O를 없앤다. 이렇게 하더라도 해당 index가 삭제되었는지 확인하기 위해 Hash Function + 탐색 시간이 overhead로 발생한다.
결국 DB가 어떻게 구성되어 있으며, 어떠한 문제가 발생하고 이를 어떠한 측면에서 접근하였는지 등에 대해 고민할 수 있는 문제이다.


다른 하나의 문제는 Z 명령이다.
복구의 경우 삭제의 역순으로 진행이 되었다. 가장 최근에 진행한 작업을 먼저 처리하는 stack 방식이다.
Browser의 방문 페이지, 프로그램의 Ctrl+Z 등의 기능처럼 역순으로 작업이 처리가 되어야 하는 것이다.
이 때, 이러한 서비스에서 각 작업에 대해 얼마나 많은 정보를 저장하고 있는 것일까?
Browser라면 방문 페이지에 대한 정보를 저장하겠으나, 접속시 어떠한 session을 사용하였고 connection에 대한 정보는 남아있을까?
글이나 댓글을 쓰는 작업 중 페이지를 변경했다면 이러한 작업에 대한 데이터는 얼마나 유지하고 있으며, 모든 데이터가 유지된다면 이를 저장하는 공간은 얼마나 주어지는가?
프로그램의 작업은 바로 윗줄과 동일하다.
결국 이 문제는 각 작업의 어느 부분까지 유지를 시키며, 작업이 많아져 허용되는 Memory를 넘길 경우 어떠한 처리를 해주고, 얼마나 이를 보장해주어야 하는지 등에 대해 고민할 수 있다.


단순한 코딩 테스트 문제임에도, 많은 부분을 고민할 수 있었다.

프로그램

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

using std :: vector ;
using std :: string ;
using std :: stack ;

struct dLinkNode
{
    int iIndex ;
    dLinkNode * pPrev ;
    dLinkNode * pNext ;

    dLinkNode ( int iIndex , dLinkNode * pPrev , dLinkNode * pNext )
        : iIndex ( iIndex ) , pPrev ( pPrev ) , pNext ( pNext ) {}
} ;

string solution ( int n , int k , vector < string > cmd )
{
    string answer = "" ;
    int iCommandSize = cmd.size () ;
    dLinkNode * pRoot = new dLinkNode ( -1 , NULL , NULL ) ;
    dLinkNode * pNode = pRoot ;
    dLinkNode * pTemp = pNode ;
    stack < dLinkNode * > sDelete ;



    for ( int i = 0 ; i < n ; ++i )
    {
        dLinkNode * pNew = new dLinkNode ( i , pTemp , NULL ) ;
        pTemp -> pNext = pNew ;
        pTemp = pNew ;
    }
    pNode = pRoot ;
    for ( int i = 0 ; i <= k ; ++i )
        pNode = pNode -> pNext ;

    for ( int i = 0 ; i < iCommandSize ; ++i )
    {
        string strCommand = cmd [ i ] ;

        if ( 'D' == strCommand [ 0 ] )
        {
            int iCount = stoi ( strCommand.substr ( 2 ) ) ;

            for ( int j = 0 ; j < iCount ; ++j )
                pNode = pNode -> pNext ;
        }
        else if ( 'U' == strCommand [ 0 ] )
        {
            int iCount = stoi ( strCommand.substr ( 2 ) ) ;

            for ( int j = 0 ; j < iCount ; ++j )
                pNode = pNode -> pPrev ;
        }
        else if ( 'C' == strCommand [ 0 ] )
        {
            sDelete.push ( pNode ) ;
            pTemp = pNode ;

            if ( pNode -> pNext )
                pNode = pNode -> pNext ;
            else
                pNode = pNode -> pPrev ;

            if ( pTemp -> pNext )        // Not the end
            {
                pTemp -> pNext -> pPrev = pTemp -> pPrev ;
            }
            if ( pTemp -> pPrev )        // Not the begin
            {
                pTemp -> pPrev -> pNext = pTemp -> pNext ;
            }

            if ( pTemp == pRoot )
                pRoot = pRoot -> pNext ;
        }
        else
        {
            dLinkNode * pNew = sDelete.top () ;

            if ( pNew -> pPrev )        // Not the Head
                pNew -> pPrev -> pNext = pNew ;
            if ( pNew -> pNext )        // Not the tail
                pNew -> pNext -> pPrev = pNew ;

            sDelete.pop () ;
        }
    }

    pNode = pRoot -> pNext ;
    for ( int i = 0 ; i < n ; ++i )
    {
        if ( ! pNode || ( i < pNode -> iIndex ) )
            answer += 'X' ;
        else
        {
            answer += 'O' ;
            pNode = pNode -> pNext ;
        }
    }


    return answer ;
}