9429. Directory
Code Battle (`23 동계 대학생 S/W 알고리즘 특강 기초학습 문제)
본 게시글은 개인 학습 용도로 작성한 게시글입니다.
(문제 출처: SW Expert Academy)
- 트리 구조로 디렉터리 구조를 구현.
- 제약사항을 분석하여 함수별로 목표로 할 시간복잡도를 정하고 풀이를 시작함.
- 테스트케이스당 $50,000$번까지 호출이 있을 수 있고, 이 중에서
cmd_cp()의 호출 횟수는 $10\%$ 이하를 차지한다. 총 10개의 테스트케이스가 있으므로 함수 별 호출 횟수를 대략적으로 유추해본다면 다음과 같다:init(): $10$회cmd_mkdir(): $(45,000 / 4) \times 10 = 112,500$회cmd_rm(): $(45,000 / 4) \times 10 = 112,500$회cmd_mv(): $(45,000 / 4) \times 10 = 112,500$회cmd_find(): $(45,000 / 4) \times 10 = 112,500$회cmd_cp(): $(5,000) \times 10 = 50,000$회
- 테스트케이스당 생성될 수 있는 디렉토리의 개수 $N$은 최대 $50,000$이다.
- 각 함수 별 목표로 할 시간복잡도를 다음과 같이 정하였다.
init(): $O(N)$ 이하cmd_mkdir(): $O(\log{N})$cmd_rm(): $O(\log{N})$cmd_mv(): $O(\log{N})$cmd_find(): $O(\log{N})$cmd_cp(): $O(N)$ 이하
- 5가지 함수 모두 주어진 경로를 이용하여 원하는 노드를 검색해 추가/수정/제거 작업을 해야한다. 이를 위해
find()를 정의했으며, 해당 함수는 $O(\log{N \times n(children)})$시간에 루트 노드로 부터 검색 대상인 노드를 찾아나간다. 자식노드의 개수는 최대 $30$개 이므로 사실상 $O(\log{N})$ 시간에 수행된다고 볼 수 있다. cmd_find()에서는 하위 디렉토리의 개수(크기)를 구해야 한다.- 완전탐색을 통해 구하게 되면 $O(N)$시간이 걸리므로, 목표인 $O(\log{N})$에 수행할 수 없게 된다.
- 디렉터리 구조가 수정될 때 각 노드의 크기를 미리 구해두는 방법을 사용한다. 자식노드의 추가/제거가 있을 때 마다 $O(\log{N})$시간에 조상 노드들의 크기를 갱신한다.
- 조상노드에 빠르게 접근하기 위해, 각 노드에는 부모 노드를 가리키는
par속성을 추가하여 사용한다.
- 자식노드를 빠르게 생성하고 제거할 수 있도록 하기위해, 형제 노드간에 Double-linked list를 적용하였다. 형제간 노드의 삽입과 삭제를 $O(1)$에 수행할 수 있으며, 부모 노드는 연결 리스트의 HEAD만 알고 있으면 되므로 공간 효율도 좋다. 다만, 형제 노드의 삽입/제거 후 부모 노드의 크기를 갱신하는데 $O(\log{N})$ 시간이 걸리는 것에 유의.
cmd_mkdir()은 삽입,cmd_rm()는 제거,cmd_mv()는 제거+삽입,cmd_find()는 접근이다. 접근/삽입/제거는 $O(\log{N})$에 수행이 가능하다.cmd_cp()는 노드의 크기만큼 삽입을 반복하므로 $O(N)$의 시간이 걸리지만, 나머지 작업은 모두 $O(\log{N})$ 시간에 수행된다.
- 테스트케이스당 $50,000$번까지 호출이 있을 수 있고, 이 중에서
#include <iostream>
#define NAME_MINLEN 2
#define NAME_MAXLEN 6
#define PATH_MAXLEN 1999
#define DIRECTORY_MAXCREATE 50000
#define DIRECTORY_MAXCHILDREN 30
// The below commented functions are for your reference. If you want
// to use it, uncomment these functions.
int mstrcmp(const char *a, const char *b)
{
int i;
for (i = 0; a[i] != '\0'; i++)
{
if (a[i] != b[i])
return a[i] - b[i];
}
return a[i] - b[i];
}
int mstrncmp(const char *a, const char *b, int len)
{
for (int i = 0; i < len; i++)
{
if (a[i] != b[i])
return a[i] - b[i];
}
return 0;
}
int mstrlen(const char *a)
{
int len = 0;
while (a[len] != '\0')
len++;
return len;
}
void mstrcpy(char *dest, const char *src)
{
int i = 0;
while (src[i] != '\0')
{
dest[i] = src[i];
i++;
}
dest[i] = src[i];
}
void mstrncpy(char *dest, const char *src, int len)
{
for (int i = 0; i<len; i++)
{
dest[i] = src[i];
}
dest[len] = '\0';
}
struct DirectoryNode {
char name[NAME_MAXLEN+1];
int size;
DirectoryNode* par;
DirectoryNode* children;
DirectoryNode* prev;
DirectoryNode* next;
};
DirectoryNode nodes[DIRECTORY_MAXCREATE+1];
DirectoryNode* new_node;
DirectoryNode* root;
void init(DirectoryNode* target, const char name[NAME_MAXLEN+1]) {
target->size = 1;
target->par = nullptr;
target->children = nullptr;
target->prev = nullptr;
target->next = nullptr;
mstrcpy(target->name, name);
}
DirectoryNode* create(const char name[NAME_MAXLEN+1]) {
DirectoryNode* cur = new_node++;
init(cur, name);
return cur;
}
void addChild(DirectoryNode* parent, DirectoryNode* child) {
if (parent->children != nullptr) {
parent->children->prev = child;
}
child->par = parent;
child->next = parent->children;
parent->children = child;
while (parent != nullptr) {
parent->size += child->size;
parent = parent->par;
}
}
void removeChild(DirectoryNode* parent, DirectoryNode* child) {
if (child == parent->children) {
parent->children = child->next;
}
if (child->prev != nullptr) {
child->prev->next = child->next;
}
if (child->next != nullptr) {
child->next->prev = child->prev;
}
child->par = nullptr;
child->prev = nullptr;
child->next = nullptr;
while (parent != nullptr) {
parent->size -= child->size;
parent = parent->par;
}
}
void remove(DirectoryNode* target) {
removeChild(target->par, target);
}
DirectoryNode* findChild(DirectoryNode* parent, const char name[NAME_MAXLEN+1]) {
DirectoryNode* child = parent->children;
while (child != nullptr) {
if (mstrcmp(child->name, name) == 0) {
return child;
}
child = child->next;
}
return nullptr;
}
DirectoryNode* ensureFindChild(DirectoryNode* parent, const char name[NAME_MAXLEN+1]) {
DirectoryNode* child = findChild(parent, name);
if (child == nullptr) {
child = create(name);
addChild(parent, child);
}
return child;
}
DirectoryNode* deepCopy(DirectoryNode* source) {
DirectoryNode* par = create(source->name);
for (DirectoryNode* child = source->children; child != nullptr; child = child->next) {
addChild(par, deepCopy(child));
}
return par;
}
DirectoryNode* find(const char path[PATH_MAXLEN + 1]) {
DirectoryNode* cur = root;
char name[NAME_MAXLEN + 1] = { '\0' };
const char *name_ptr = path;
int name_len = 0;
if (*name_ptr == '/') {
name_ptr++;
}
while (*name_ptr != '\0') {
if (*name_ptr != '/') {
name[name_len++] = *name_ptr;
name[name_len] = '\0';
} else {
cur = findChild(cur, name);
name_len = 0;
}
name_ptr++;
}
return cur;
}
// n = ~50,000
// calls: 10
void init(int n) {
new_node = nodes+1;
root = nodes;
init(root, "");
}
// calls: 112,500
// goal: O(log(N))
void cmd_mkdir(char path[PATH_MAXLEN + 1], char name[NAME_MAXLEN + 1]) {
addChild(find(path), create(name));
}
// calls: 112,500
// goal: O(log(N))
void cmd_rm(char path[PATH_MAXLEN + 1]) {
remove(find(path));
}
// calls: 50,000
// goal: O(N)
void cmd_cp(char srcPath[PATH_MAXLEN + 1], char dstPath[PATH_MAXLEN + 1]) {
addChild(find(dstPath), deepCopy(find(srcPath)));
}
// calls: 112,500
// goal: O(log(N))
void cmd_mv(char srcPath[PATH_MAXLEN + 1], char dstPath[PATH_MAXLEN + 1]) {
DirectoryNode* src = find(srcPath);
removeChild(src->par, src);
addChild(find(dstPath), src);
}
// calls: 112,500
// goal: O(log(N))
int cmd_find(char path[PATH_MAXLEN + 1]) {
return find(path)->size - 1;
}