[LeetCode] Evaluate Division 자바

문제

 

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

 

▫️equations[i] = [Ai, Bi]

▫️ values[i] = Ai / Bi

▫️ queries의 각 변수 쌍은 나눈 값들을 리턴하라

       구할 수 없다면 -1.0 리턴하라

 

 

문제 풀이

 

처음 보고 든 생각은 주어진 분자 분모의 조합으로 나올 수 있는 모든 값들을 저장해두고 queries 반복하면서 도출해내고 저장해둔 값이 없으면 -1로 해야겠다고 생각했다. 그런데 주어진 equations과 values로 모든 경우의 조합을 구하는 코드를 작성하기가 어려워서 결국 다른 사람의 코드를 보고 공부했다.. 구현 아이디어가 어마어마하다..아이디어는 같지만 구현하기가 어려웠다. (대단한 사람들..)

 

✅ 알고리즘

1. equations을 for문으로 돌면서 분모와 분자, 그리고 해당 값을 담을 수 있는 HashMap을 생성한다

 Map(분자, (분모, 값))

  (a, (b, 2.0) )

  (b, (a, 1.0 / 2.0) )

  (b, (c, 3.0) )

  (c, (b, 1.0 / 3.0) )

 

2. 위의 과정을 통해 알 수 있는 모든 값을 저장 한 후 이제 queries를 for문으로 돌면서 하나씩 DFS 함수를 호출하여 답을 도출한다

 여기서 포인트는 분모가 분자에 있으면 소거가 가능하여 새로운 수식 도출이 가능하다는 것이다.

 

3. 구하려고하는 분자(key값)에 있는 분모 map(value값)을 가져와서 다시 분자 파라미터로 넣어서 DFS를 호출한다

 answer값은 해당 map의 value값과 곱하여 갱신해 파라미터로 넣어준다

 

💡HashMap의 putIfAbsent 함수

  : key값이 있는 경우 value 반환
    key값이 없는 경우 key, value 저장 후 null 반환

 

소스 코드

 

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        double[] answer = new double[queries.size()];
		HashMap<String, HashMap<String, Double>> map = new HashMap<>();
		
		//Map(분자, (분모, 값))
		for(int i = 0; i < equations.size(); i++) {
			String start = equations.get(i).get(0);
			String end = equations.get(i).get(1);
			double value = values[i];
			
			map.putIfAbsent(start, new HashMap<>());
			map.putIfAbsent(end, new HashMap<>());
			
			map.get(start).put(end, value);
			map.get(end).put(start, 1.0 / value);
		}
        
		for(int i = 0; i < queries.size(); i++) {
			String node = queries.get(i).get(0);
			String des = queries.get(i).get(1);
			//equations에 값이 없는 것 -1 리턴
			if(!map.containsKey(node) || !map.containsKey(des))
				answer[i] = -1.0;
			else {
				HashSet<String> visited = new HashSet<>();
				double[] ans = {-1.0};
				double temp = 1.0;
				DFS(node, des, map, visited, ans, temp);
				answer[i] = ans[0];
			}
		}
		
        return answer;
    }
	
	public static void DFS(String node, String des, HashMap<String, HashMap<String,Double>> map, HashSet<String> visited, double[] ans, double temp) {
		//이미 방문한 노드라면
		if(visited.contains(node))
			return;
		
		visited.add(node);
		
		//현재 노드가 목적지와 같으면 지금까지 곱해진 값 리턴
		if(node.equals(des)) {
			ans[0] = temp;
			return;
		}
		
		//노드와 연결된 다음 노드들을 돈다
		for(Map.Entry<String, Double> entry: map.get(node).entrySet()) {
			String next = entry.getKey();
			double val = entry.getValue();
			DFS(next, des, map, visited, ans, temp * val);
		}
    }
}