Portfolio

📄문제

399. Evaluate Division

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Example 1:


Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation:
Given:a / b = 2.0,b / c = 3.0
queries are:a / c = ?,b / a = ?,a / e = ?,a / a = ?,x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]

Example 2:


Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:


Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

✏️풀이

은찬


const calcEquation = (equations, values, queries) => {
    const map = new Map();
    
    for(let i = 0; i < equations.length; i++){
        const A = equations[i][0];
        const B = equations[i][1];
        
        if(!map.get(A)){
            map.set(A, new Map());
        }
        
        if(!map.get(B)){
            map.set(B, new Map());
        }
        
        map.get(A).set(A, 1);
        map.get(B).set(B, 1);
        map.get(A).set(B, values[i]);
        map.get(B).set(A, 1 / values[i]);
    }
    
    // 플로이드 와샬
    map.forEach((_, k) => {
        map.get(k).forEach((_, i) => {
            map.get(k).forEach((_, j) => {
                map.get(i).set(j, map.get(i).get(k) * map.get(k).get(j));
            })
        })
    })
    
    return queries.map( ([ A, B ]) => map.get(A) ? map.get(A).get(B) || -1 : -1)
};

재영


const calcEquation = (equations, values, queries) => {
  const names = {};
  let cnt = 0;
  // 현재 name들을 index로 묶어준다.
  equations.forEach(([from, to]) => {
    if (!names.hasOwnProperty(from)) {
      names[from] = cnt;
      cnt += 1;
    }
    if (!names.hasOwnProperty(to)) {
      names[to] = cnt;
      cnt += 1;
    }
  });

  // keyLength를 받아 플로이드 와샬에 필요한 array를 만들어 준다.
  const keyLength = Object.keys(names).length;

	// 초기는 0으로 설정.
  const arr = Array.from({ length: keyLength }, () =>
    new Array(keyLength).fill(0)
  );

  // array에 간선 값을 담아준다.
  equations.forEach(([from, to], idx) => {
    arr[names[from]][names[to]] = values[idx];
    arr[names[to]][names[from]] = 1 / values[idx];
  });

  // 여기가 어려웠음.
  for (let i = 0; i < keyLength; i += 1) {
    for (let j = 0; j < keyLength; j += 1) {
      if (i === j) arr[i][j] = 1; // 항상 1이될 수밖에 없다.
      for (let k = 0; k < keyLength; k += 1) {
        if (arr[j][k]) continue;
        arr[j][k] = arr[j][i] * arr[i][k];
      }
    }
  }

  // 요구 사항에 맞춰 답을 반환한다.
  return queries.map(([from, to]) => {
    if (names[from] === undefined || names[to] === undefined) return -1;
    else return arr[names[from]][names[to]] || -1;
  });
};

효성


var calcEquation = function(equations, values, queries) {
    const calcMap = new Map();
    equations.flat().forEach(key => !calcMap.has(key) && calcMap.set(key, new Map()));
    
    equations.forEach((equation, idx) => {
        const [numerator, denominator] = equation;
        calcMap.get(numerator).set(denominator, values[idx]);
        calcMap.get(denominator).set(numerator, 1/values[idx]);
    });
    
    for(const [first, firstMap] of calcMap) {
        for(const [second, fstDivSec] of firstMap) {
            const secondMap = calcMap.get(second);
            for(const [third, secDivTrd] of secondMap) {
                const thirdMap = calcMap.get(third);
                const fstDivTrd = fstDivSec*secDivTrd;
                firstMap.set(third, fstDivTrd);
                thirdMap.set(first, 1/fstDivTrd);
            }
        }
    }
    
    return queries.map(query => {
        const [numerator, denominator] = query;
        return calcMap.get(numerator)?.get(denominator) ?? -1;
    });
};