[99클럽 코테 스터디 25일차 TIL] Evaluate Division - Java [자바][LeetCode]

 

 

📜 문제 내용

 

🤔 과정

• 문제를 읽고 고민하다가 부모 노드 관계와 합집합 개념이 연관되어 있는 Union-Find 알고리즘을 이용하면 될 것 같다고 판단했다. 하지만 Union-Find 구현이 생각나지 않아 학습을 다시 하고 진행했다. 

 

✨ 최초 제출 답안 - 🙆‍♂️ 통과

class Solution {
    private Map<String, String> node;
    private Map<String, Double> value;

    public double[] calcEquation(
        List<List<String>> equations, double[] values, List<List<String>> queries) {
        int eqLen = equations.size();
        node = new HashMap<>();
        value = new HashMap<>();

        // 초기 설정 
        for (List<String> eq : equations) {
            node.put(eq.get(0), eq.get(0));
            node.put(eq.get(1), eq.get(1));
            value.put(eq.get(0), 1.0);
            value.put(eq.get(1), 1.0);
        }

        // Union 처리
        for (int i = 0; i < eqLen; i++) {
            List<String> eq = equations.get(i);
            String a = eq.get(0);
            String b = eq.get(1);

            // a,b의 루트 찾기
            String pa = find(a);
            String pb = find(b);

            if (pa.equals(pb)) {
                continue;
            }

            // 루트가 다르면 a,b 합치기 
            node.put(pa, pb);
            value.put(pa, value.get(b) * values[i] / value.get(a));
        }

        // 쿼리 계산
        int qrLen = queries.size();
        double[] ans = new double[qrLen];
        
        for (int i = 0; i < qrLen; i++) {
            String c = queries.get(i).get(0);
            String d = queries.get(i).get(1);

            // 쿼리 속 변수가 모두 존재하고, 같은 루트에 있는지 확인 
            ans[i] = !node.containsKey(c) || !node.containsKey(d) || !find(c).equals(find(d))
                ? -1.0
                : value.get(c) / value.get(d);
        }

        return ans;
    }

    // Find 처리(x의 루트를 찾기)
    // 루트가 다르면 x의 부모 노드를 찾고 가중치 업데이트 
    private String find(String x) {
        if (!x.equals(node.get(x))) {
            String origin = node.get(x);

            node.put(x, find(node.get(x)));
            value.put(x, value.get(x) * value.get(origin));
        }

        return node.get(x);
    }
}

 

• Union - Find 알고리즘에 대한 학습을 진행했다. 

 

🔗 문제 링크

• LeetCode - Evaluate Division (링크)