[Java / Kotlin] 99 클럽 코딩 테스트 스터디 미들러 25일차 - Evaluate Division

https://leetcode.com/problems/evaluate-division/description/

[문제]

주어진 식(equations)과 값(values)은 두 변수 간의 나눗셈 관계를 나타냅니다.

예를 들어, equations [i] = [Ai, Bi]와 values [i] = k가 주어지면, 이는 "Ai / Bi = k"를 의미합니다.

즉, Ai를 Bi로 나눈 값이 k라는 뜻입니다.

이때, queries[j] = [Cj, Dj]가 주어지면, "Cj / Dj"의 값을 계산하여 그 결과를 반환해야 합니다.

만약 해당 식을 계산할 수 없는 경우에는 -1.0을 반환합니다.

 

[입출력 예시]

1. 입력:
   • equations = [["a", "b"], ["b", "c"]]
   • values = [2.0, 3.0]
   • queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]
2. 설명:
   • a / b = 2.0 (a를 b로 나눈 값은 2.0이다)
   • b / c = 3.0 (b를 c로 나눈 값은 3.0이다)
   주어진 쿼리에 대해 계산을 해보면:
   • a / c = ? -> a / b * b / c = 2.0 * 3.0 = 6.0
   • b / a = ? -> b / a = 1 / (a / b) = 1 / 2.0 = 0.5
   • a / e = ? -> e는 주어진 변수에 없으므로, -1.0을 반환합니다.
   • a / a = ? -> a를 a로 나누면 무조건 1.0입니다.
   • x / x = ? -> x는 주어진 변수에 없으므로, -1.0을 반환합니다.

따라서, 최종 출력은 [6.0, 0.5, -1.0, 1.0, -1.0]이 됩니다.

 

[풀이]

해당 문제는 그래프 탐색 문제로 접근이 가능합니다. DFS (깊이 우선 탐색)를 활용하여 풀이를 진행했습니다.

각 Pair의 변수들은 그래프 노드로 취급하고, 변수 사이의 비율을 간선으로 간주해야 합니다.

 

코틀린 코드로 풀이를 진행합니다.

탐색을 위한 그리프를 먼저 생성해주어야 합니다.

// 그래프를 표현하는 자료구조
private val graph = mutableMapOf<String, MutableMap<String, Double>>()

키 문자와 비율을 포함하는 Map을 Value로 취급하는 Map을 만들어줍니다.

 

private fun addEdge(a: String, b: String, value: Double) {
    graph.computeIfAbsent(a) { mutableMapOf() }[b] = value
    graph.computeIfAbsent(b) { mutableMapOf() }[a] = 1 / value
}

computeIfAbsent를 활용하여 유효 값이 존재하면 반환, 없다면 기본 계산 값을 반환합니다.

이를 통해 그래프에 간선을 추가하게 됩니다.

예를 들어, a / b = 2.0이라면 그래프에는 a -> b 에는 2.0, b -> a 에는 1 / 2.0이 추가됩니다.

 

private fun dfs(start: String, end: String, visited: MutableSet<String>): Double {
    if (!graph.containsKey(start) || !graph.containsKey(end)) return -1.0
    if (start == end) return 1.0
    visited.add(start)

    for ((next, value) in graph[start]!!) {
        if (next !in visited) {
            val result = dfs(next, end, visited)
            if (result != -1.0) {
                return result * value
            }
        }
    }
    return -1.0
}

두 변수 간 경로 탐색을 위해 DFS 함수를 구성합니다.

시작 변수에서 끝 변수까지 경로를 탐색하고 각 비율을 계산합니다.

if (!graph.containsKey(start) || !graph.containsKey(end)) return -1.0

만약 그래프에서 시작 노드 또는 끝 노드가 없다면 유효하지 않은 경로이므로 바로 -1.0을 반환합니다.

if (start == end) return 1.0

시작 노드와 끝 노드가 동일한 값이면 자기 자신을 의미하므로 1.0을 반환합니다.

그래프 탐색은 이미 방문한 노드인지를 확인하기 위해 visited 변수로 시작 노드를 체크해주어야 합니다.

visited.add(start) //mutableSetOf()를 초기값으로 활용

 

그리고 방문하지 않은 노드만을 체크하여 dfs 함수의 재귀호출을 통해 유효한 상태의 노드일 경우 비율을 반환하도록 합니다.

for ((next, value) in graph[start]!!) {
    if (next !in visited) {
        val result = dfs(next, end, visited)
        if (result != -1.0) {
            return result * value
        }
    }
}

 

이제 먼저 그래프를 생성해 주고, 생성한 그래프를 기반으로 탐색 함수를 호출해 주면 되겠습니다.

fun calcEquation(equations: List<List<String>>, values: DoubleArray, queries: List<List<String>>): DoubleArray {
    // 그래프 구성
    for (i in equations.indices) {
        val (a, b) = equations[i]
        addEdge(a, b, values[i])
    }

    val result = DoubleArray(queries.size)
    for (i in queries.indices) {
        val (a, b) = queries[i]
        result[i] = dfs(a, b, mutableSetOf())
    }

    return result
}

 

전체 코드입니다.

class Solution {
    private val graph = mutableMapOf<String, MutableMap<String, Double>>()

    private fun addEdge(a: String, b: String, value: Double) {
        graph.computeIfAbsent(a) { mutableMapOf() }[b] = value
        graph.computeIfAbsent(b) { mutableMapOf() }[a] = 1 / value
    }

    private fun dfs(start: String, end: String, visited: MutableSet<String>): Double {
        if (!graph.containsKey(start) || !graph.containsKey(end)) return -1.0
        if (start == end) return 1.0
        visited.add(start)

        for ((next, value) in graph[start]!!) {
            if (next !in visited) {
                val result = dfs(next, end, visited)
                if (result != -1.0) {
                    return result * value
                }
            }
        }
        return -1.0
    }

    fun calcEquation(equations: List<List<String>>, values: DoubleArray, queries: List<List<String>>): DoubleArray {
        for (i in equations.indices) {
            val (a, b) = equations[i]
            addEdge(a, b, values[i])
        }

        val result = DoubleArray(queries.size)
        for (i in queries.indices) {
            val (a, b) = queries[i]
            result[i] = dfs(a, b, mutableSetOf())
        }

        return result
    }
}

 

아래는 자바 코드입니다.

import java.util.*;

class Solution {
    private final Map<String, Map<String, Double>> graph = new HashMap<>();

    private void addEdge(String a, String b, double value) {
        graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, value);
        graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / value);
    }

    private double dfs(String start, String end, Set<String> visited) {
        if (!graph.containsKey(start) || !graph.containsKey(end)) return -1.0;
        if (start.equals(end)) return 1.0;
        visited.add(start);

        for (Map.Entry<String, Double> entry : graph.get(start).entrySet()) {
            String next = entry.getKey();
            double value = entry.getValue();
            if (!visited.contains(next)) {
                double result = dfs(next, end, visited);
                if (result != -1.0) {
                    return result * value;
                }
            }
        }
        return -1.0;
    }

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        for (int i = 0; i < equations.size(); i++) {
            List<String> equation = equations.get(i);
            String a = equation.get(0);
            String b = equation.get(1);
            addEdge(a, b, values[i]);
        }

        double[] result = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            List<String> query = queries.get(i);
            String a = query.get(0);
            String b = query.get(1);
            result[i] = dfs(a, b, new HashSet<>());
        }

        return result;
    }
}