🙆‍♀️

コーディングテスト

2024/07/14に公開

某企業のテスト

ちゃんと勉強しよう

``````class Huffman:
def __init__(self):
self.tree = None
self.pattern = None
self.encode_dict = {}

def encode(self, data):
unique_data = set(data)
nodes = []

for v in unique_data:
node_obj = Node(value=v, count=data.count(v))
nodes.append(node_obj)
temp = []

if len(nodes) == 1:
self.encode_dict[nodes[0].value] = "1"
self.tree = nodes[0]
return "1" * len(data)

while len(nodes) >= 2:
for v in range(2):
elem = min(nodes, key=lambda x: x.count)
temp.append(elem)
nodes.remove(elem)
n = Node(value=None, count=temp[0].count+temp[1].count, left=temp[0], right=temp[1])
temp = []
nodes.append(n)
self.tree = nodes[0]
self.recursive_code(self.tree, "")
s = ""
for v in data:
s += self.encode_dict[v]
return s

def recursive_code(self, node, s):
if not isinstance(node, Node):
return
if node.value:
self.encode_dict[node.value] = s

return
self.recursive_code(node.right, s+"1")
self.recursive_code(node.left, s+"0")

class Node:
def __init__(self, value=None, count=None, left=None, right=None):
self.value = value
self.left = left
self.right = right
self.count = count

h = Huffman()
input = input()
x = h.encode(input)

for i in '0123456789':
if i in h.encode_dict:
print(i, h.encode_dict[i])

else:
print(i, 'null')
``````