99클럽 코테 스터디 25일차 TIL + 오늘의 학습 키워드

☑️ 문제(Leetcode): 399. Evaluate Divistion

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

 

☑️ 설계

우선 이 문제의 핵심은 어떻게 "str1 / str2 = x.x"의 값을 구할 수 있냐인데,

a/b = 2.0, b/c = 3.0라고 할 때, a/c의 값은 a/c = (a/b * b/c)로 구할 수 있다.

처음에는 아래 조건을 만족하는 것을 완전 탐색으로 찾으려고 하였다.

(정보를 가지고 있는 값을 num1/num2, num3/num4 그리고 구하고자 하는 값을 answer1 / answer2라고 하겠다.)

1. answer1 == num1
2. answer2 == num4
3. num2 == num3

그런데 문제 유형이 그래프라는 사실을 보고 아래 방식으로 그래프를 그려보았다.

a/b = 2.0를 a -> b (가중치: 2.0)

b/c = 3.0를 b -> c (가중치: 3.0)

그랬더니 a/c의 값은, (a->b의 가중치 * b->c의 가중치) 값과 같다는 사실을 알 수 있었다.

즉, 가중치를 가지고 있는 방향 그래프로 나타낼 수 있다는 사실을 깨달을 수 있었고,

구하고자 하는 값은 x에서 y까지 이동할 수 있는 경로가 있는지 그래프 탐색을 해보고,

탐색했을 때 경로가 있다면, 경로 가중치를 모두 곱한 값이 정답이다.

반대로 경로가 존재하지 않는다면, -1를 출력하면 된다.

 

이 사실을 가지고 설계를 진행해보았다.

'더보기'에서 설계 내용을 확인할 수 있다.

// 1. HashMap을 사용해서 "a", "cd" 등 equations에서 나오는 문자열을 int로 mapping

 

// 2. Map 크기만큼 인접 배열 초기화 (node 수 = map 크기)

 

// 3. 인접 배열에 weight 값 할당 (weight[a][b] = a -> b의 가중치 값 = a / b의 values 값)

// (1) weight[i][i](자기 자신)에 1.0 할당

// (2) 인접 배열에 values값 할당 (a / b -> weight[a][b] = values)

 

// 4. queries 각 내용을 구할 수 있는지, 그래프 탐색(dfs, bfs)으로 확인

// (1) 탐색 가능, return weight * ... * weight

// (2) 탐색 불가능, return -1

 

☑️ 후기

문제가 나한테 난이도가 있고 다른 더 급하게 처리할 일이 있어서, 설계까지만 해보았다🥲

나는 설계보다는 구현력이 아직 부족하다는 걸 느낄 수 있었다.

다른 사람들의 풀이를 참고해보니, 일단 방향성은 맞는 듯 하니 구현 실력을 기르기 위해서 주말에 꼭 연습해보자.