[Leet Code] Throne Inheritance

문제가 풀면서 약간 삼성전자 역량테스트 B형 냄새가 살짝 베어있는 듯한 느낌이 드는 문제다.
사실 B형 치고는 시간복잡도적인 측면에 있어서 제한을 많이 안둔게 특징인 것 같다.

정말 오랜만에 그동안 묵혀뒀던 CPP를 꺼내 들어서 썻다.
코드가 상당히 지저분할수 있으니 애도를....
주소는 여기에

문제 파악

왕국에 왕이있고, 왕이 또 자식을 낳고.. 그 자식들이 계속해서 또 자식을 낳게 되는데,
예를들어 가장 첫번째 왕이, A, B ,C, D의 아이를 낳았다고 치면
왕, A,B,C,D의 순서이고,
여기서 또 A가 자식을 AA,AB, AC를 낳게되면

왕,A,AA,AB,AC,B,C,D 의 순서로 밀어넣게된다.

태어날때마다 부모와 자식의 정보를 링크드 리스트 형태로 밀어넣게 되면 문제가 간단하게 해결될 것이다.

Hash

먼저, birth, init, death등 들어오는 인풋값들이 전부 이름이고, 이름의 글자수는 소문자로만 이루어진 최대 15개의 글자를 사용한다.

해시 테이블을 만드는것도 해볼법한 일이지만 CPP 에서 long long을 선언해서 담는 것을 상상했는데,

long long Hash(string name) {
	long long ret = 0;
    int i = 0;
    while(name[i]) {
    	ret = (ret << 5) + (name[i] - 'a' + 1);
	}
    return ret;
}

의 방식을 사용해서 하게되면 최대 65비트를 사용하게되고 오버플로우가 나는지라 저런식으로 해시테이블을 만들어서 사용하지 않기로했다. (귀찮으니까!)

나는 Unordered_map을 사용해서 해결했다.

문제 해결과정

함수별로 각개 격파하자.

구조체 선언

struct Node {
    string name;
    int n = 0;
    bool death;
    Node *prev, *next;
    Node *child, *parent;

}buf[100010];
int idx = 0;

이름, 그리고 자식을 갖고있는지 확인하는 n, 죽었는지 판단하는 death로 구성했다.
보통 n을 잘안쓰는데.. 릿코드에서 빈 노드 확인할때 nullptr 에러가 나서 구분용으로 사용했다.

buf를 저런식으로 선언해놓는데는 이유가 다있다.

보통 링크드리스트를 직접 한땀한땀 New나 malloc, calloc 키워드를 사용해서 선언하는데 사실 알고리즘 문제풀이할때 있어서 메모리적인 요소의 제한이 크지 않다면 그냥 정적으로 배열 선언해둔것에서 하나 하나 가져다 쓰는것이 훨씬 빠르고 관리하기 쉽다.

buf 의 index별 관리는 idx로 한다.

ThroneInheritance 생성자

unordered_map<string, Node*> map;
string king = "";
ThroneInheritance(string kingName) {
	buf[idx] = {kingName, 0, 0,0, 0, 0, 0};
	map[kingName] = &buf[idx++];
	king = kingName;
}

처음 생성할때 buf[idx]를 사용하여, map의 kingName Key에 해당하는 곳에 넣어주도록 한다.
또한, 최초의 왕의이름을 king이라는 string 변수를 선언해서 담아둔다.

birth

void birth(string parentName, string childName) {
	Node *p = map[parentName];

        buf[idx] = {childName, 0,0, 0,0, map[parentName]};
        map[childName] = &buf[idx];
        if(p->n != 0){
            p->child->prev = &buf[idx];
            buf[idx].next = p->child;
        }
        p->child = &buf[idx];
        p->n = 1;
        idx+= 1;
}

Birth함수는 parentName과, childName이 들어오게 되고 이 관계를 정립하는것이 핵심이다.
먼저 해야할것은, 아직 생성되어있지 않은 childName에 해당하는 요소를 생성하는 것이다.
buf를 통해 parent Node를 parentName이 가지고있는 Item을 향하도록 선언해주고, childName Key값에 해당하는 Item에 넣어주게 된다.

그리고 부모 노드의 자식 노드가 있을 경우
1. 현재 부모노드의 자식노드의 prev의 방향을 childName의 아이템 방향으로 향하게 놓는다.
2. childName에 아이템의 next의 방향을 현재 parent이 자식 방향으로 향하게 한다.
3. parent의 자식을 childName 아이템으로 만들어준다.

일련의 과정을 그림으로 보면 다음과 같다.

이미 old child가 parent 부모의 child노드를 차지하고있다.
이것을 코드같이 하나씩 바꿔보겠다.

먼저 old child의 prev노드를 신규 추가할 new Child Node를 바라보게한다.

그리고, new child node가 old child node를 바라보게한다.

마지막으로, parent 노드의 child가 new child node를 가리키도록 만들어주면 된다.
이런식으로 하게 되면 굴러들어온 돌이 박힌돌을 빼내는 것 같은 느낌이 들게끔 만들어줄수 있다.

아마 이러한 방식의 최종지향점은

이러한 형태다.

어찌되었든, 이러한 식으로 쌓게 되면 들어온 역 순서대로 방출하게 되는것을 알아두자.

death

void death(string name) {
        Node *p = map[name];
        p->death = true;
}

아마도 제일 간단한 함수가 아닐까?.. 그냥 죽었는지만 체크하면 된다.

getInheritanceOrder

void getID(Node *name, vector<string> &ans) {
        if(!name){ return ;}
        Node *sibling = name;
        for(; sibling->next; sibling = sibling->next){
        }
        for(; sibling; sibling = sibling->prev) {
            if(!sibling->death)
                ans.push_back(sibling->name);
            if(sibling->n)
                getID(sibling->child, ans);
        }    
}

vector<string> getInheritanceOrder() {
        vector<string> ans;
        if(!map[king]->death)
            ans.push_back(king);
        if(map[king]->n)
            getID(map[king]->child, ans);
        return ans;
}

이제 순회하면서 모든 왕족의 정보를 ans에 담아서 리턴을 해줘야하는데
그냥 평소 dfs를 하듯 타고가면 된다.
애초에 10번 호출되는 함수이고, 최악 N이 10 * 2인것을 감안하면 무리없는 풀이다.

getID를 통해 아이디의 Sequence를 잡아준다.
자식 노드가 생길때 거꾸로 생겼으니, 거꾸로 가서 최초 지점부터 시작하여 순회하고 ans에 값을 넣어 출력한다.

전체코드 는 여기에 있다.

후기

오랜만에 역량테스트 B형이 생각나는 문제였다.
아마 진짜 B형이였다면 getInheritanceOrder를 완전탐색하게 두진 않을 문제를 냈을거같은데
간만에 자료구조가지고 이것저것하는 재밌는 문제였다.