[leetCode/JS] 756. Pyramid Transition Matrix

난이도 [ 🤔 ] Medium

 

문제 설명 

 

You are stacking blocks to form a pyramid. Each block has a color, which is represented by a single letter. Each row of blocks contains one less block than the row beneath it and is centered on top. 

 

To make the pyramid aesthetically pleasing, there are only specific triangular patterns that are allowed. A triangular pattern consists of a single block stacked on top of two blocks. The patterns are given as a list of three-letter strings allowed, where the first two characters of a pattern represent the left and right bottom blocks respectively, and the third character is the top block. 

• For example, "ABC" represents a triangular pattern with a 'C' block stacked on top of an 'A' (left) and 'B' (right) block. Note that this is different from "BAC" where 'B' is on the left bottom and 'A' is on the right bottom. 

You start with a bottom row of blocks bottom, given as a single string, that you must use as the base of the pyramid. 

 

Given bottom and allowed, return true if you can build the pyramid all the way to the top such that every triangular pattern in the pyramid is in allowed, or false otherwise.

 

 

당신은 블록을 쌓아 피라미드를 만들고 있습니다. 각 블록은 하나의 알파벳 문자로 표시되는 색깔을 가지고 있습니다. 각 블록 층은 바로 아래층보다 블록이 하나 적으며, 아래층의 중앙 위에 놓입니다.
피라미드를 미적으로 아름답게 만들기 위해 허용되는 특정한 '삼각형 패턴'이 정해져 있습니다. 삼각형 패턴은 두 개의 블록 위에 하나의 블록을 쌓는 방식입니다. 이 패턴들은 allowed라는 세 글자 문자열 리스트로 제공되는데, 처음 두 글자는 각각 아래층의 왼쪽과 오른쪽 블록을 나타내고, 세 번째 글자는 그 위에 쌓이는 블록을 나타냅니다.
예를 들어 "ABC"라는 패턴은 왼쪽 'A'와 오른쪽 'B' 블록 위에 'C' 블록을 쌓는 것을 의미합니다. 이는 'B'가 왼쪽이고 'A'가 오른쪽인 "BAC"와는 다르다는 점에 유의하세요.
당신은 bottom이라는 문자열로 주어진 맨 아랫줄 블록들을 피라미드의 기초로 사용해야 합니다.
bottom과 allowed가 주어졌을 때, 피라미드의 모든 삼각형 패턴이 allowed에 포함된 규칙을 따르면서 꼭대기까지 피라미드를 완성할 수 있으면 true를, 그렇지 않으면 false를 반환하세요.

주어진 바닥(bottom)에서 시작해서, 허용된 규칙(allowed)에 맞는 블록들만 쌓아 올려 결국 꼭대기(블록 1개)까지 도달할 수 있는지 묻는 문제

 

입출력 예

Example 1:

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"] 
Output: true 
Explanation: The allowed triangular patterns are shown on the right. Starting from the bottom (level 3), 
we can build "CE" on level 2 and then build "A" on level 1. There are three triangular patterns in the pyramid, 
which are "BCC", "CDE", and "CEA". All are allowed.

 

Example 2:

 

Input: bottom = "AAAA", allowed = ["AAB","AAC","BCD","BBE","DEF"] 
Output: false Explanation: The allowed triangular patterns are shown on the right. 
Starting from the bottom (level 4), there are multiple ways to build level 3, but trying all the possibilites, you will get always stuck before building level 1.

 

Constraints

• 2 <= bottom.length <= 6 
• 0 <= allowed.length <= 216 
• allowed[i].length == 3 The letters in all input strings are from the set {'A', 'B', 'C', 'D', 'E', 'F'}. 
• All the values of allowed are unique.

 

 

 

---

내 솔루션

• 층별 재귀와 다음 피라미드를 만드는 재귀를 2개 만들어야 한다는 생각을 하는게 정말 오래 걸렸다.
• AAAA의 경우의 수가 AA -> B, C 중 1개를 선택해서 만들어야 하는 예시2를 안보여줬다면 영원히 걸렸을 지도 모른다ㅋㅋ
• 마지막에 Map()인 memo를 만든다면 속도 100% 달성 가능하다. 아니면 70%대

/**
 * https://leetcode.com/problems/pyramid-transition-matrix
 * @param {string} bottom - 피라미드의 맨 아랫줄 문자열
 * @param {string[]} allowed - 사용 가능한 [왼쪽, 오른쪽, 위] 패턴 리스트
 * @return {boolean} - 꼭대기까지 쌓을 수 있는지 여부
 */
var pyramidTransition = function (bottom, allowed) {
    
    // 1. [데이터 구조화] "왼쪽+오른쪽" 2글자를 키로, 위에 올 수 있는 "후보 문자들"을 배열로 저장
    // 예: "AA": ["B", "C"] 형태
    const patterns = allowed.reduce((acc, [left, right, top]) => {
        const key = left + right;
        acc[key] = (acc[key] || []);
        acc[key].push(top);
        return acc;
    }, {});

    // 2. [메모이제이션] 이미 확인한 '층(문자열)'의 결과를 저장해 중복 계산 방지
    // 키: "AAB", 값: true/false
    const memo = new Map();

    /**
     * [층 단위 재귀 함수]
     * 현재 층을 완성하고, 그 다음 윗층으로 올라가는 역할
     */
    const canSolve = (curr) => {
        // 꼭대기(길이 1)에 도달했다면 피라미드 건설 성공!
        if (curr.length === 1) return true;
        
        // 이 층 구성은 이미 검사해본 적이 있다면 저장된 결과를 반환
        if (memo.has(curr)) return memo.get(curr);

        // 현재 층(curr)을 기반으로 다음 층(nextRow)을 한 칸씩 쌓기 시작
        const result = buildRow(curr, "", 0);
        
        // 현재 층에서 꼭대기까지 갈 수 있는지 여부를 메모리에 기록
        memo.set(curr, result);
        return result;
    }

    /**
     * [칸 단위 재귀 함수] - 백트래킹의 핵심
     * 현재 층(curr)의 블록들을 조합해 바로 윗층(nextRow) 한 줄을 만드는 역할
     * @param {string} curr - 기준이 되는 아래층
     * @param {string} nextRow - 현재 만들어지고 있는 윗층 문자열
     * @param {number} idx - 아래층에서 검사할 블록의 시작 인덱스
     */
    const buildRow = (curr, nextRow, idx) => {
        // 윗층의 길이가 아래층보다 1 작게 완성되었다면 (한 줄 완성)
        if (nextRow.length === curr.length - 1) {
            // 완성된 줄을 '현재 층'으로 삼아 다시 윗층 쌓기 시도 (층 단위 재귀 호출)
            return canSolve(nextRow);
        }

        // 현재 검사 중인 두 블록(왼쪽, 오른쪽)으로 만들 수 있는 패턴 키 생성
        const key = curr[idx] + curr[idx + 1];
        const currentPattens = patterns[key] || [];

        // 가능한 모든 후보 문자('char')를 하나씩 대입해보며 탐색
        for (const char of currentPattens) {
            // 후보 문자를 윗층에 추가하고, 다음 칸(idx + 1)을 채우러 이동
            if (buildRow(curr, nextRow + char, idx + 1)) {
                // 이 경로로 끝까지 도달하는 데 성공했다면 즉시 true 반환 (가지치기)
                return true;
            }
        }
        
        // 모든 후보를 써봤지만 윗층을 완성할 수 없다면 false
        return false;
    }

    // 맨 처음 바닥(bottom)부터 피라미드 쌓기 시작
    return canSolve(bottom);
};

 

감상평

• 왐마 준내 어렵다.
• 리트코드 미디엄 수준으로 코테가 나오면 1시간에 1개도 못풀지도 모른다.