13501. 수열 편집

Code Battle (`23 동계 대학생 S/W 알고리즘 특강 기초학습 문제)

본 게시글은 개인 학습 용도로 작성한 게시글입니다.
(문제 출처: SW Expert Academy)

Doubly-linked list를 사용하여 풀이.
std::list를 사용할 경우, 동적 할당으로 인해 실행시간이 길어지므로, 직접 doubly-linked list를 구현하고 노드를 정적으로 할당하여 사용하였다.
테스트케이스의 개수 $T$, 수열의 길이 $N$, 쿼리의 수 $M$에 대하여, 이 풀이의 시간복잡도는 $O(T(N+M(N+M)))$이다.¹
수열의 크기는 최대 $N+M$이다 (모든 작업이 삽입일 경우).
임의의 원소에 접근하는데 걸리는 시간이 $O(N+M)$이고, 삽입・삭제・수정하는 작업은 $O(1)$시간에 수행이 가능하다.
임의의 원소에 접근하는 동작을 $O(\frac{N+M}{2})$에 수행 가능하도록 개선하였다. (doubly-linked list의 head와 tail 중 더 가까운 곳에서 출발하도록 하였다.)

#include <iostream>

#define CMD_INSERT 'I'
#define CMD_DELETE 'D'
#define CMD_CHANGE 'C'

#define MAX_N 1000
#define MAX_M 1000

struct node {
    int data;
    node *prev;
    node *next;
};

node *nodeHead;
node *nodeTail;
int nodeCount;
int nodePoolPointer;
node nodePool[MAX_N + MAX_M + 1];

void clearNodes() {
    nodePoolPointer = 0;
    nodeCount = 0;
    nodeHead = nullptr;
    nodeTail = nullptr;
}

node *makeNode(int data) {
    node *newNode = nodePool + nodePoolPointer++;
    newNode->data = data;
    newNode->prev = nullptr;
    newNode->next = nullptr;
    return newNode;
}

node *findNode(int index) {
    node *currentNode;
    if (index < (nodeCount >> 1)) {
        currentNode = nodeHead;
        for (int i = 0; i < index; i++) {
            currentNode = currentNode->next;
        }
    } else {
        currentNode = nodeTail;
        for (int i = nodeCount - 1; i > index; i--) {
            currentNode = currentNode->prev;
        }
    }
    return currentNode;
}

void pushBackNode(int data) {
    node *newNode = makeNode(data);
    node *prevNode = nodeTail;
    if (prevNode != nullptr) {
        prevNode->next = newNode;
        newNode->prev = prevNode;
    } else {
        nodeHead = newNode;
    }
    nodeTail = newNode;
    nodeCount++;
}

void pushFrontNode(int data) {
    node *newNode = makeNode(data);
    node *nextNode = nodeHead;
    if (nextNode != nullptr) {
        newNode->next = nextNode;
        nextNode->prev = newNode;
    } else {
        nodeTail = newNode;
    }
    nodeHead = newNode;
    nodeCount++;
}

node *popFrontNode() {
    node *targetNode = nodeHead;
    node *nextNode = targetNode->next;
    if (nextNode != nullptr) {
        nextNode->prev = nullptr;
    } else {
        nodeTail = nullptr;
    }
    nodeHead = nextNode;
    nodeCount--;
    return targetNode;
}

node *popBackNode() {
    node *targetNode = nodeTail;
    node *prevNode = targetNode->prev;
    if (prevNode != nullptr) {
        prevNode->next = nullptr;
    } else {
        nodeHead = nullptr;
    }
    nodeTail = prevNode;
    nodeCount--;
    return targetNode;
}

void insertNode(int data, int index) {
    if (index == 0) {
        pushFrontNode(data);
        return;
    }
    node *newNode = makeNode(data);
    node *nextNode = findNode(index);
    node *prevNode = nextNode->prev;
    nextNode->prev = newNode;
    newNode->prev = prevNode;
    prevNode->next = newNode;
    newNode->next = nextNode;
    nodeCount++;
}

void removeNode(int index) {
    if (index == 0) {
        popFrontNode();
        return;
    }
    if (index == nodeCount-1) {
        popBackNode();
        return;
    }
    node *targetNode = findNode(index);
    node *nextNode = targetNode->next;
    node *prevNode = targetNode->prev;
    prevNode->next = nextNode;
    nextNode->prev = prevNode;
    nodeCount--;
}

void updateNode(int data, int index) {
    node *targetNode = findNode(index);
    targetNode->data = data;
}

int getNodeValue(int index) {
    if (0 <= index && index < nodeCount) {
        return findNode(index)->data;
    }
    return -1;
}

static int solveTestCase()
{
    int size, query, index;
    clearNodes();
    std::cin >> size >> query >> index;
    for (int i = 0; i < size; i++)
    {
        int value;
        std::cin >> value;
        pushBackNode(value);
    }
    for (int i = 0; i < query; ++i)
    {
        char cmd;
        int index, value;
        std::cin >> cmd;
        switch (cmd)
        {
        case CMD_INSERT:
            std::cin >> index >> value;
            insertNode(value, index);
            break;
        case CMD_DELETE:
            std::cin >> index;
            removeNode(index);
            break;
        case CMD_CHANGE:
            std::cin >> index >> value;
            updateNode(value, index);
            break;
        default:
            break;
        }
    }
    return getNodeValue(index);
}

static void solve()
{
    int T;
    std::cin >> T;
    for (int testCaseNo = 1; testCaseNo <= T; testCaseNo++) {
        fprintf(stdout, "#%d %d\n", testCaseNo, solveTestCase());
    }
    return;
}

int main(int argc, char** argv)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    // freopen("sample_input.txt", "r", stdin);
    // freopen("sample_output.txt", "w", stdout);
    solve();
    return 0;
}

최악의 경우 $O(50,025,000)$ 정도가 걸리는 것으로 볼 수 있는데, 시간 제한 1초에 굉장히 근접하다. ↩