[python] 계층적 구조의 다중 필터링

코테 문제를 풀다 효율적인 계층적 구조의 다중 필터링 알고리즘이 필요해서 여기에 기록해둔다.

예를 들어 8명이 각각 A, B, C, D 요소를 갖고 있다고 할 때,

첫 번째 필터로 가장 큰 A요소를 가진 사람을 찾고,

만약 여러 명이면 그 여러 명 중에서 가장 큰 B요소를 가진 사람을 찾고,

여기서도 여러 명이면 가장 작은 C요소를 가진 사람을 찾고

여기서도 여러 명이면 가장 작은 D요소를 가진 사람을 찾는 문제를 "계층적 구조의 다중 필터링" 알고리즘이라 칭했다. 각 필터가 독립적이지 않고 조건부로 얽혀있기 때문이다.

좀 많이 고민했는데, 현재 기준 가장 깔끔한 것 같은 알고리즘 구상은 아래와 같다. 상위 필터에서 단독으로 걸리는 가정은 생략했다.

dic = {"A": [5, 5, 5, 5, 3, 5, 2, 1],
       "B" : [4, 4, 1, 4, 4, 4, 5, 3],
       "C" : [4, 3, 1, 2, 2, 2, 5, 2],
       "D" : [3, 1, 2, 2, 4, 5, 3, 5]}

best_A = max(dic["A"]) # 5
best_A_indices = [i for i, ele in enumerate(dic["A"]) if ele == best_A] # [0, 1, 2, 3, 5]
best_B = max([ele for i, ele in enumerate(dic["B"]) if i in best_A_indices]) # 4
best_B_indices = [i for i, ele in enumerate(dic["B"]) if ele == best_B and i in best_A_indices] # [0, 1, 3, 5]
best_C = min([ele for i, ele in enumerate(dic["C"]) if i in best_B_indices]) # 2
best_C_indices = [i for i, ele in enumerate(dic["C"]) if ele == best_C and i in best_B_indices] # [3, 5]
best_D = min([ele for i, ele in enumerate(dic["D"]) if i in best_C_indices]) # 2
best_D_indices = [i for i, ele in enumerate(dic["D"]) if ele == best_D and i in best_C_indices] # [3]