LeetCode 756 Pyramid Transition Matrix - with Trie (트라이)

https://leetcode.com/problems/pyramid-transition-matrix/

Pyramid Transition Matrix - LeetCode

필자는 재귀 안에 또 다른 재귀가 돌아가야하는 구조로 생각하였다. 근데 그렇게 하여도 시간초과가 나서 트라이 구조까지 끼얹었다.

 

가장 바닥에 있는 문자열(문제에서는 bottom으로 표현)이 주어졌을 때, 일단 다음 bottom을 만들어야 한다. 필자는 풀이에서 bot이라고 명명했다. bot의 길이가 1이 되면 최종 성공으로 판정된다.  bot 길이가 1이 될때까지 반복한다. 그 과정이 1차 재귀가 된다. 먼저 내부에서 bot을 채워야 하는데 그것이 2차 재귀가 된다.

 

이 재귀함수들의 탈출조건을 설정해야 한다.

먼저 2차 재귀는 다음 bot이 다 채워졌을 때일 것이다. 다음 bot이 다 채워졌는지는 현재의 bot길이보다 1 작은 만큼의 길이를 갖게 되었을 때로 판단한다.

다음 1차 재귀의 탈출 조건은 위에서 말했듯이 bot의 길이가 1일 경우이다. 이 말은 가장 최상위까지 모든 칸을 성공적으로 채웠다는 것이고, true를 리턴하여 승리(?) 성공했음을 알리게 된다.

 

여기까지 풀이 설계를 하는 것도 쉽지는 않았다. 항상 완료 후에 슬쩍 다시 볼때는 별거 아닌것 같이도 보이는데 처음 코드를 쓸 때는 생각을 많이 해야한다. 하지만 이렇게 해도 시간 초과가 났다. 그 이유는 allowed 배열을 일일이 확인하고 있기 때문이었다. allowed 배열의 길이는 최대 216인데 이는 6곱하기 6곱하기 6에서 왔다. 문자가 6가지 이므로.

어쨌든 매 단계에서 216씩 확인하므로 첫 bottom이 6일 경우, ( 216 * 5) * ( 216 * 4 ) * ( 216 * 3 ) * ... * ( 216 * 1 )의 시간복잡도를 갖는다 ㄷㄷ. 

 

이를 해결하기 위해 트라이( Trie )자료구조를 도입했다. 처음 주어지는 allowed배열의 원소를 하나하나 트라이에 등록하여두고, 다음 bot을 채우는 과정(위에서 말한 2차 재귀 부분)에서 어떤 문자들만 확인하면 되는지를 구했다. 

예를 들면, allowed = ["AAB","AAC","BCD","BBE","DEF"] 인 경우,

하단 bot의 두 문자가 AA일 때는 B와 C만 체크하면 된다. 

좌측에서 보다시피, AA트리안에는 B, C만 있기 때문에 2개만 확인하면 된다.

BBE, BCD, DEF는 볼 필요도 없는 것이다.

좌측과 같이, 트라이 구조를 만들고, 앞 두 문자로 찾아 들어가서 나오는 key(s)를 배열로 받아 확인하도록 수정했다. 

트라이 자료구조에 대해서는 다음에 따로 포스팅할 계획이다. 일단은 여러 문자열을 트리구조로 구성한다고 생각하면 된다.

 

이제 시간 복잡도를 크게 줄일 수 있었다.

 

 

 

 

 

 

 

<알고리즘>

DFS(재귀함수), Trie

 

<코드>

Javascript

let trie = {}

const reset = _ => {
    trie = {}
}

const register = (word, i, curr) => {
    if (i === word.length) return
    if (!(word[i] in curr)) {
        curr[word[i]] = {}
    }
    register(word, i + 1, curr[word[i]])
}

const check = s => {
    let i = 0, curr = trie
    while (i < s.length) {
        if (!(s[i] in curr)) return [false, null]
        curr = curr[s[i++]]
    }
    return [true, Object.keys(curr)]
}

const fill = (bot, i, g) => {
    if (bot.length === 1) return true
    if (bot.length - 1 === g.length) return fill(g.join(''), 0, [])

    let [flag, chars] = check(bot.slice(i, i + 2))
    if (!flag) return false
    for (const char of chars) {
        g.push(char)
        if (fill(bot, i + 1, g)) return true
        else g.pop()
    }
    return false
}

/**
 * @param {string} bottom
 * @param {string[]} allowed
 * @return {boolean}
 */
var pyramidTransition = function (bottom, allowed) {
    reset()
    for (const e of allowed) register(e, 0, trie)
    return fill(bottom, 0, [])
};

 

fill이 1차, 2차 재귀를 모두 수행하는 함수이다. check 함수는 flag와 chars를 리턴하는데 flag(지금 생각해보니 chars하나만 리턴해도 된다.)가 false면 일치하는 triple이 없다는 것이고, true면 일치하는 가능한 문자들을 배열로 묶어서 내려준다.

register함수는 트라이 자료구조에 allowed내 문자들을 하나씩 등록하는 역할을 한다.