Division 코딩 문제 솔루션 평가

Source: Dev.to

Evaluate Division Overview

Evaluate Division은 대수식처럼 보이는 그래프 문제입니다. 다음과 같은 방정식 목록이 주어집니다:

a / b = 2.0
b / c = 3.0

그리고 다음과 같은 질의가 있습니다:

a / c = ?
c / a = ?
x / x = ?

당신의 작업은 방정식이 암시하는 관계를 이용해 각 질의의 결과를 계산하는 것입니다. 주어진 정보만으로 답을 구할 수 없는 경우 -1.0을 반환합니다.

핵심 아이디어는 변수를 가중 그래프의 노드로 취급하는 것입니다. 각 방정식은 두 변수 사이의 직접 변환 비율을 제공하므로, 문제는 노드 사이의 경로를 찾고 그 경로를 따라 간선 가중치를 곱하는 것으로 바뀝니다.

What Makes It Tricky

• Unordered equations – 방정식은 어떤 순서로든 나타날 수 있어, 질의를 답하기 위해 여러 번 점프해야 할 수 있습니다.
• Disconnected components – 일부 변수는 다른 변수와 전혀 연결되지 않을 수 있습니다.
• Missing variables – 질의에 방정식에 한 번도 등장하지 않은 변수가 포함될 수 있으며, 이런 경우 즉시 -1.0을 반환해야 합니다.

Solution Idea Expected by Interviewers

Model the Equations as a Weighted Graph

• 각 변수를 노드로 간주합니다.
• 방정식 u / v = k에 대해 두 개의 방향 간선을 추가합니다:
  • u → v 가중치 k
  • v → u 가중치 1 / k

역방향 간선은 나눗셈 관계가 역전될 수 있기 때문에 필수입니다.

Answer Queries Using Graph Traversal

각 질의 x / y에 대해:

1. Check existence – x 또는 y 중 하나라도 그래프에 없으면 -1.0을 반환합니다.
2. Search for a path – x에서 y까지 깊이‑우선 탐색(DFS) 또는 너비‑우선 탐색(BFS)을 수행합니다.
   • 실행 중인 곱셈값을 1.0으로 초기화합니다.
   • 간선을 통과할 때마다 그 간선의 가중치와 곱합니다.
   • y에 도달하면 현재 곱셈값이 정답이 됩니다.
3. Avoid cycles – 현재 탐색 동안 무한 루프를 방지하기 위해 visited 집합을 유지합니다.

Special Cases

• Self‑division (x / x)
  • x가 그래프에 존재한다면 결과는 1.0입니다.
  • x가 존재하지 않으면 -1.0을 반환합니다.

Why This Approach Is Efficient in Interviews

• Graph construction – 방정식 수 E에 대해 선형 시간 O(E)으로 그래프를 만들 수 있습니다.
• Query processing – 각 질의는 탐색되는 연결 컴포넌트에 대해 최악의 경우 O(V + E) 시간이 소요되며, 이는 일반적인 인터뷰 제한 내에서 충분히 빠릅니다.
• Scalability – 질의가 많을 경우 결과를 캐시하거나 가중 합집합(Disjoint Set) 구조를 사용해 반복 탐색을 줄일 수 있지만, 대부분의 인터뷰어는 직관적인 탐색 솔루션만으로도 만족합니다.

Common Mistakes to Avoid

• Omitting the reciprocal edge – 역방향 질의가 깨집니다.
• Not using a per‑query visited set – 순환 그래프에서 무한 재귀 또는 중복 작업이 발생할 수 있습니다.
• Returning 1.0 for x / x when x is unknown – 이 경우 올바른 응답은 -1.0입니다.

Related Coding Problem Solutions

• Maximum Sum Circular Subarray
• Coin Change II