[C++] Programmers Lv. 3 "표 편집"

🔵 문제 링크

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

프로그래머스

💡 Point

• 삭제 - 복구를 어떻게 하는가?
• U, D 커맨드 시 삭제된 행을 효율적으로 건너뛰는 방법

🔷 삭제 - 복구를 어떻게 하는가?

삭제했던 행 중 가장 최근의 것을 복구하므로 스택을 떠올렸다.

삭제할 행의 인덱스를 스택에 push 하고, 복구할 때는 스택의 top에 있는 인덱스를 가져오고 pop 한다.

 

🔷 U, D 커맨드 시 삭제된 행을 효율적으로 건너뛰는 방법

처음 풀 때 위 사항을 간과하고 풀었다.

표를 vector로 구현하고 삭제되었는지 여부만 vector에 표시하여 풀었다.

U, D 커맨드를 할 때 while문으로 현재 행이 삭제된 행인지 일일이 확인하면 되겠지라는 생각이었다.

    // 삭제된 건 건너뛰고 세기
    while (i < n)
    {
        ret--;
        if (isDeleted[ret] == true)
            continue;
        i++;
    }

 

하지만 표의 행 개수를 n이라 할 때, 최악의 경우 삭제된 것을 건너 뛰고 세는 while 루프 안에서만 O(n)이 걸릴 수 있다.

왜냐하면 표의 행이 삭제되었다 하더라도 실제 표를 담고 있는 vector에는 삭제된 행이 남아 있었고, 이것을 while문으로 일일이 확인하기 때문이다.

 

🔵 새로운 방식 - 양방향 연결 리스트

vector로 표를 구현하는 방식으론 시간 복잡도 이슈를 해결하지 못할 것 같았다.

그래서 삽입, 삭제가 O(1)인 연결 리스트 방식으로 풀어 보았다.

 

vector 자료구조로는 삽입, 삭제가 비효율적이라 표에 직접 적용하지 못했다.

하지만 삽입, 삭제가 O(1)인 연결 리스트라면 실제 표의 행을 삽입, 삭제할 수 있을 거고, 그렇다면 해당 연결 리스트로 구현한 표에 U, D 커맨드를 실행할 때 현재 행이 삭제된 행인지 일일이 검사할 필요가 없어지는 것이다. 

즉, U X라는 커맨드가 주어졌을 때, 시간 복잡도가 O(X)가 되는 것을 보장받을 수 있다.

 

🔷 양방향 연결 리스트를 vector로 구현해 보기

    vector<int> prev(n);
    vector<int> next(n);

    for (int i = 0; i < n; i++)
    {
        prev[i] = i - 1;
        next[i] = i + 1;
    }

 

prev, next vector를 만들어 인덱스마다 prev, next 정보를 담았다.

예를 들어 3행의 prev는 prev[3]에 담겨 있고, 3행의 next는 next[3]에 담겨 있는 것이다.

참고로 첫 행의 prev는 -1로, 마지막 행의 next는 n으로 하여 나중에 예외 처리할 때 사용한다.

 

삭제, 삽입 구현은 자료 구조 책에 흔하게 있는 양방향 연결 리스트 예제를 떠올리며 구현하였다. 헷갈리면 복습해 보자!

 

🔵 전체 코드

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

// n이 100만 
// 삭제 -> 스택 push, (가장 최근)복구 -> 스택 pop 

// 커맨드 실행 시 while문으로 가리키는 항목이 삭제되었는지 일일이 확인 X
// 100만 * 20만은 시간 초과

// 삭제된 것을 어떻게 효율적으로 확인하는가? 
// 연결리스트 방법으로!

string solution(int n, int k, vector<string> cmd)
{
    vector<int> prev(n);
    vector<int> next(n);
    stack<int> deleted;

    for (int i = 0; i < n; i++)
    {
        prev[i] = i - 1;
        next[i] = i + 1;
    }

    int cur = k;

    // 명령어 뒤 U 12와 같이 두자리수가 올 수 있으므로
    // str[2] 같은 방식이 아닌 str.substr(0, 2)로 문자열을 잘라 처리
    for (string str : cmd)
    {
        if (str[0] == 'C')
        {
            deleted.push(cur);

            // 연결리스트 방식
            if (prev[cur] != -1) next[prev[cur]] = next[cur];
            if (next[cur] != n) prev[next[cur]] = prev[cur];

            // 현재 가리키는 행이 마지막인지 여부에 따라
            // 이전 행을 가리킬 것인가, 다음 행을 가리킬 것인가 처리
            cur = (next[cur] == n) ? prev[cur] : next[cur];
        }
        else if (str[0] == 'Z')
        {
            int restore = deleted.top();
            deleted.pop();

            // 연결리스트 방식
            if (prev[restore] != -1) next[prev[restore]] = restore;
            if (next[restore] != n) prev[next[restore]] = restore;
        }
        else if (str[0] == 'U')
        {
            for (int i = 0; i < stoi(str.substr(2)); i++)
                cur = prev[cur];
        }
        // D
        else
        {
            for (int i = 0; i < stoi(str.substr(2)); i++)
                cur = next[cur];
        }
    }

    string answer(n, 'O');

    // 현재 stack에 납아 있는 것만 삭제된 것임
    while (!deleted.empty())
    {
        answer[deleted.top()] = 'X';
        deleted.pop();
    }

    return answer;
}

 

🔵 stl - list는 안 되는 이유

C++ stl에서 제공하는 list로 구현해 보았지만 시간 측면에서 번번히 실패하였다.

왜인지 이유를 생각해 보았다.

 

아마 stl의 리스트는 연속된 자료구조가 아니라 시간 측면에서 실패하지 않았나 생각해 본다.

직접 vector로 구현한 양방향 연결 리스트는 연속된 자료구조여서 시간에서 훨씬 이점이 있다.

반면 stl에서 제공하는 리스트는 연속된 자료구조가 아니라 메모리 여기저기에 흩어져 있어 시간이 비교적 더 들었을 것이다.

그리고 자료에 접근할 때 vector는 임의 접근으로 O(1)이 걸리는 반면, list는 순차 접근으로, 인덱스를 n이라 할 때 O(n)이 걸리는 것도 이유가 되지 않았나 싶다.

 

🔵 시간 복잡도

n이 표 행의 개수(최대 100만), m이 명령어 개수(최대 20만)라고 할 때,

• 초기화: O(n)
• 명령어 처리: O(m) (U, D 쪽 for문은 모든 X들의 값을 합친 결과가 100만 이하라고 하였으므로 양방향 연결 리스트로 구현한 이상 상수로 가정할 수 있다.)
• 스택: O(n)

 

따라서 시간 복잡도는 O(n)이다.