Alien Dictionary

Alien Dictionary

문제 내용

의미를 알수 없는 Alien의 Dictionary 가 alien 기준의 알파벳 오름차순 기준으로 주어진다면, alien 기준의 알파벳 순서를 사용해서 사용된 chars의 순서로 word를 만들어라

 

접근 방법

words = ["wrt","wrf","er","ett","rftt"]

라는 입력이 들어왔을 때, 알파벳 순서임으로

• w < e
• e < r
• r < t
• t < f

을 추측할 수 있다.

예를 들자면 wrf보다 er이 더 작음으로 w보다 e가 알바펫 순서상으로 더 크다고 볼수 있다.

여기서 주의를 해야할 것은

• wrf와 er사이에 w와 e의 관계가 성립되었다면,
• rf와 r 사이에 관계는 더이상 무의미 하다

2번째로 주의해야 할 것은 edge 케이스 인데,

"abcd" 다음에 "ab"가 올 수도 있다. 이는 기본적인 알파벳 순서 규칙을 어기는 것임으로 진행 되어선 안된다.

이렇게 만들어진 문자간 사이를 다음과 같이 나타낼 수 있다.

이 노드들의 관계를 topology sort를 통해서 가장 우선적으로 삭제 되어야할 node부터 처리 하면 된다.

상기 그림 순서로 보면 $ w < e < r < t < f $ 순서가 된다.

이른 위상정렬이라고 부른다.

즉 Node를 Pointing하고 있는 대상이 없을 경우, 해당 노드를 가장 먼저 삭제 하면 된다.

w를 삭제하고

자신을 Pointing 하고 있는 Count가 없는 e를 입력해 주면 된다. 이런 방식으로 

• wertf

가 답이 된다.

코드는 아래와 같다.

var alienOrder = function (words) {
    if(words.length < 1) return "";

    let charMap = new Map();
    let topology = new Map();
    let result = "";

    for (let word of words) {
        for(let char of word){
            charMap.set(char, 0);
            topology.set(char, new Array());
        }
    }

    for (let i = 0; i < words.length - 1; i++) {
        let firstWord = words[i];
        let secondWord = words[i + 1];

        //Edge Case : input에 abc, ab가 들어올 경우 sorted lexicographically에 맞지 않는다.
        if (firstWord.length > secondWord.length && firstWord.startsWith(secondWord)) {
            return ""; // fail 처리가 필요하다.
        }

        // 모든 char를 순환하면서 edge를 build 한다.
        for (let j = 0; j < Math.min(firstWord.length, secondWord.length); j++) {
            if (firstWord.charAt(j) !== secondWord.charAt(j)) {
                charMap.set(secondWord.charAt(j), charMap.get(secondWord.charAt(j)) + 1);
                topology.get(firstWord.charAt(j)).push(secondWord.charAt(j));
                break;
            }
        }

    }

    let queue = new Array();

    for(let [key,value] of charMap){
        if (value === 0) {
            queue.push(key);
        }
    }

    while (0 < queue.length) {
        let key = queue.shift();

        result += key;

        let neighbors = topology.get(key);

        neighbors.map((item)=>{
            let count = charMap.get(item) - 1;
            charMap.set(item, count);
            if(count === 0){
                queue.push(item);
            }
        });
    }

    if(result.length < charMap.size) return "";

    return result;
};

시간 복잡도가 계산하기 어렵다.

모든 words의 length를 더한 값이 시간 복잡도라고 한다.

$$ O(SumOfLengths) $$