[Algorithm]Find all sampling from nested dictionary of list

문제:

주어진 dictionary의 key는 string, value는 list거나 dictionary이다.

이 때,

list인 경우는 element가 정수이고 size가 1이상이다.

dictionary인 경우는 마찬가지로 key가 string이고 value가 dictionary거나 list이다.

이 때, 원래의 dictionary의 nested structure는 유지하면서, list에서 1개의 원소를 꺼낸 가능한 모든 dictionary를 list로 반환하는 함수를 작성하여라.

 

ex)

dic1 = {'a':[1,2], 'b':[3], 'c':{'e':[4,5], 'd':{'e':[6,7], 'f':[8]}}}

이 때, 반환값은 list이고 각 원소는

{'a': 1, 'b': 3, 'c': {'e': 4, 'd': {'e': 6, 'f': 8}}}
{'a': 1, 'b': 3, 'c': {'e': 4, 'd': {'e': 7, 'f': 8}}}
{'a': 1, 'b': 3, 'c': {'e': 5, 'd': {'e': 6, 'f': 8}}}
{'a': 1, 'b': 3, 'c': {'e': 5, 'd': {'e': 7, 'f': 8}}}
{'a': 2, 'b': 3, 'c': {'e': 4, 'd': {'e': 6, 'f': 8}}}
{'a': 2, 'b': 3, 'c': {'e': 4, 'd': {'e': 7, 'f': 8}}}
{'a': 2, 'b': 3, 'c': {'e': 5, 'd': {'e': 6, 'f': 8}}}
{'a': 2, 'b': 3, 'c': {'e': 5, 'd': {'e': 7, 'f': 8}}}

 

해결:

비고:

-실제 업무에서 RandomizedSearch를 구현하는 데에 필요하여 작성함

-비교적 간단한 재귀인데도, 생각보다 시간이 필요했다.

-필요한 함수들을 침착하게 만들다보면 해결됨

-dictionary를 merge하는 것은 python 3.9에서는 union operator를 사용할 수 있지만, 이전 버전에서는 {**dic1, **dic2}라는 못생긴 방법으로 해야함