[Python] Advent of Code 2022 - Day 7
Part One
이번 인풋에는 폴더를 탐색하는 커맨드가 한 줄 씩 적혀있고,
현재 읽고 있는 폴더 트리에서 폴더의 크기가 100,000 이하인 것들의 데이터 크기의 합을 구해내는 게 이번 과제이다.
일단 파일경로를 파악하기 위해 폴더 트리를 만들어야 했고 어떤 데이터 타입으로 만들까 하다 nested dictionary로 정하였다.
단순히 값을 나열해야하는 게 아니라 어떤 경로를 가진 어떤 폴더에 얼만큼의 파일이 있는지 알아내야 했기 때문이다.
예시에 나온 폴더로 예상 폴더 트리의 모습을 짜보자면,
nested_dict = {
"a": {
"e": {
"i" : 584
},
"f": 29116,
"g": 2557,
"h.lst" : 62596
},
"b.txt": 14848514,
"c.dat": 8504156,
"d" : {
"j": 4060174,
"d.log": 8033020,
"d.ext": 5626152,
"k": 7214296
}
}이런 식으로 폴더 트리가 만들어져야 한다. (폴더 일 경우 { "폴더이름" : 폴더 혹은 파일 }, 파일 일 경우 { "파일이름" : 파일의 크기 })
내가 만들 데이터의 모습을 생각해냈으니, 이제 그 데이터가 어떤 과정을 통해 만들어져야 하는지 구상해내야 했다.
우리가 가져올 인풋의 각 라인들에 적혀있는 것은 크게 보자면 $가 붙어 있는 것과 붙어 있지 않은 것으로 나뉘어진다.
$가 붙은 것은 커맨드로 실행이 되어야 하는 것이고, $가 붙지 않은 것은 단순 나열된 데이터로 현재 탐색하는 폴더에 어떤 파일과 폴더가 있는지 보여준다.
1. 일단 $가 앞에 붙어있는지 안 붙어있는지 확인하기
1-1. $가 앞에 붙어 있다면 그 다음 오는 것을 확인하기
1-1-1. cd <name> : 이름이 "name"인 폴더에 들어감
1-1-2. cd .. : 해당 폴더에서 밖으로 나옴
1-1-3. ls : 폴더에 담겨있는 데이터들을 나열시킴
1-2. $가 앞에 붙어 있지 않다면
1-2-1. 앞에 숫자가 오는 경우: 파일이기 때문에 뒤에 오는 문자를 key로 앞에 오는 숫자를 value로 dict에 담기
1-2-2. 앞에 숫자가 오지 않는 경우(dir가 있는 경우): dir 다음에 오는 문자를 key로 하고 빈 dict을 value로 넣기
여기서 문제는 현재 폴더의 경로가 어떻게 되는지 파악하는 것이었다.
그 경로를 알아야 폴더 안으로도 들어가고 밖으로도 나올 수 있기 때문이다. 이를 위해서 current_path 라는 리스트를 만들었다.
current_path = [ ]
1. cd <name> 가 실행되면 <name>을 current_path에 append 한다
1-1. 예: 위의 예시 폴더에서 폴더 "e"에 있다면, current_path = ["a", "e"] 이렇게 담긴다
2. cd .. 가 실행되면 current_path에서 가장 마지막 것을 지워준다.
3. current_path에 담겨있는 걸 활용하여 해당하는 위치에 값을 넣을 수 있게 한다.
3-1. 예: nested_dict["a"]["e"] = xxx
결국 구해야하는 것은 폴더 트리 그 자체가 아니라 폴더들 중 크기가 100,000이하인 걸 찾아 그 폴더들의 데이터 크기 합을 구해내는 것이었기 때문에 그 데이터 크기의 합을 구하는 과정도 생각해내야했다. 이를 위해 새로운 딕셔너리인 dir_dict를 만들었다.
dir_dict = { }
1. 구성은 폴더 트리랑 같지만 각 폴더(딕셔너리)에 key는 "sum", value로 폴더의 크기만 적혀있게 한다.
1-1. 예: {"a": {"e": {"sum" : 584}}}
2. 이때 파일이 들어 있는 그 폴더 뿐만 아니라 경로에 해당되는 모든 폴더에 데이터의 크기가 들어가야 한다.
2-1. current_path를 활용하여 해당 경로 폴더 모두에 폴더의 크기를 넣어준다.
2-1-1. 예: {"a": {"sum": 584, "e": {"sum": 584}}}
3. 나중에 dir_dict의 sum만 돌면서 100,000 이하인 것들만 추려내어 그 합을 구한다.
+ 코드를 짜보면서 깨달은 것은, tree와 dir_dict의 뼈대가 같고 결국 나중에 문제를 풀기위해 사용하는 건 dir_dict라서 사실 tree 딕셔너리는 문제를 풀기 위해서는 딱히 필요가 없는 것 같다. 하지만 코드를 짜는 중간중간 틀릴 때마다 어떤 부분에서 틀렸는지 검토해 볼 때 사용하기 좋았다.
이렇게 짠 과정들을 다음과 같이 만들어보았다.
file = open("input/day7.txt", "r")
data = file.read().splitlines()
commands = []
# 1
for line in data:
commands.append(line.split())
def get_key(dict, path):
if len(path) == 1:
return dict[path[0]]
return get_key(dict[path[0]], path[1:])
tree = {}
current_path = []
dir_dict = {}
# 2
for command in commands:
if command[0] == "$":
if command[1] == "cd":
if command[2] == ".." and len(current_path) >= 1:
del current_path[-1]
elif command[2] == "/":
pass
else:
current_path.append(command[2]) # 2-1
elif command[1] == "ls":
pass
else:
if command[0].isnumeric(): # 2-2
size = int(command[0])
if len(current_path) == 1:
tree[current_path[0]][command[1]] = size
dir_dict[current_path[0]]["sum"] += size
elif len(current_path) == 2:
get_key(tree, current_path)[command[1]] = size
dir_dict[current_path[0]]["sum"] += size
dir_dict[current_path[0]][current_path[1]]["sum"] += size
elif len(current_path) > 2:
get_key(dir_dict, current_path)["sum"] += size
for i in range(1, len(current_path)):
get_key(dir_dict, current_path[:-i])["sum"] += size
else:
tree[command[1]] = size
elif command[0] == "dir":
if len(current_path) == 0:
tree[command[1]] = {}
dir_dict[command[1]] = {"sum": 0}
elif len(current_path) == 1:
tree[current_path[0]][command[1]] = {}
dir_dict[current_path[0]][command[1]] = {"sum": 0}
else:
get_key(tree, current_path)[command[1]] = {}
get_key(dir_dict, current_path)[command[1]] = {"sum": 0}
# 3
def filter(d):
for v in d.values():
if isinstance(v, dict):
yield from filter(v)
else:
yield v
filtered_list = list(filter(dir_dict))
sum = 0
for i in filtered_list:
if i <= 100000:
sum += i
print(sum)# 1 먼저 데이터들을 띄어쓰기로 구분해서 리스트로 담고 commands 리스트에 담아준다.
>> [ [ "$", "cd", "/"], ["$", "cd", "a"], ...]
# 2 트리를 만든다. 앞서 짠 구성대로 일단 $가 붙었는지 안 붙었는지 if 로 나눠주고, 그 안에서도 cd인지 ls인지, cd라면 ..인지 /인지 이름인지, $가 아닌 경우에는 앞에 숫자가 오는지 안 오는지 이렇게 큰 틀을 잡는다.
그리고 아직 루트폴더에 있는 경우, 폴더를 하나 들어온 경우, 두 개 들어온 경우, 두 개 이상 들어온 경우 등 상황에 맞게 if/elif 를 짠다.
여기서 가장 중요한 파트는 폴더를 생성해주는 부분(#2-1), 파일을 폴더에 넣어주는 부분(#2-2)이다.
문제는, 경로를 받아와 tree["a"]["b"]["c.dat"] = 1234 이런식으로 파일을 넣어줘야 하는데, 키를 어떻게 저렇게 쌓느냐는 것이었다.
이거 때문에 시간이 엄청 오래 걸렸는데 결론적으로는 재귀함수를 사용하여 해결하였다. ( get_key() )
각 if/elif 의 구성은 다음과 같다.
파일인 경우, 먼저 폴더에 파일을 넣고 (tree), 파일의 크기를 파일크기 구하기 위한 딕셔너리인 dir_dict에 추가한다(더해준다).
폴더인 경우, 풀더를 폴더에 넣고 (tree), dir_dict에도 그 폴더를 추가한다.
# 3 위의 과정을 거쳐 폴더 트리를 만든 후, nested dictionary의 모든 key, value를 받아올 수 있는 함수를 하나 짠다. 딕셔너리를 돌며 nest 된 것들은 또 다시 함수를 거치게 하여(재귀함수) 결국 nest 된 딕셔너리에서 점점 안으로 들어가 모든 key와 value를 받아올 수 있게 한다. 그렇게 모든 폴더의 "sum" 을 받아와 filtered_list에 넣는다.
이제 filtered_list 안을 돌며 100,000 이하인 숫자들을 찾아내어 그 합을 구해주면 답이 나온다.
Part Two
이번엔 전체 파일시스템의 크기인 70,000,000에서 적어도 unused space가 30,000,000이 되어야 하는데, 이를 위해 지워져야하는 폴더 중 가장 크기가 작은 폴더의 크기를 구해야한다.
일단 part one과 당연히 거의 동일하고 used space와 unused space를 계산하는 과정이 조금 들어갔다.
file = open("input/day7.txt", "r")
data = file.read().splitlines()
commands = []
for line in data:
commands.append(line.split())
def get_key(dict, path):
if len(path) == 1:
return dict[path[0]]
return get_key(dict[path[0]], path[1:])
tree = {}
current_path = []
dir_dict = {}
outermost = {} # new
for command in commands:
if command[0] == "$":
if command[1] == "cd":
if command[2] == ".." and len(current_path) >= 1:
del current_path[-1]
elif command[2] == "/":
pass
else:
current_path.append(command[2])
elif command[1] == "ls":
pass
else:
if command[0].isnumeric():
size = int(command[0])
if len(current_path) == 1:
tree[current_path[0]][command[1]] = size
dir_dict[current_path[0]]["sum"] += size
elif len(current_path) == 2:
get_key(tree, current_path)[command[1]] = size
dir_dict[current_path[0]]["sum"] += size
dir_dict[current_path[0]][current_path[1]]["sum"] += size
elif len(current_path) > 2:
get_key(dir_dict, current_path)["sum"] += size
for i in range(1, len(current_path)):
get_key(dir_dict, current_path[:-i])["sum"] += size
else:
tree[command[1]] = size
outermost[command[1]] = size # new
elif command[0] == "dir":
if len(current_path) == 0:
tree[command[1]] = {}
outermost[command[1]] = {} # new
dir_dict[command[1]] = {"sum": 0}
elif len(current_path) == 1:
tree[current_path[0]][command[1]] = {}
dir_dict[current_path[0]][command[1]] = {"sum": 0}
else:
get_key(tree, current_path)[command[1]] = {}
get_key(dir_dict, current_path)[command[1]] = {"sum": 0}
def filter(d):
for v in d.values():
if isinstance(v, dict):
yield from filter(v)
else:
yield v
filtered_list = list(filter(dir_dict))
# new
used_space = 0
for k, v in outermost.items():
if isinstance(v, dict) == False:
used_space += v
elif isinstance(v, dict):
used_space += dir_dict[k]["sum"]
unused_space = 70000000 - used_space
should_delete = 30000000 - unused_space
should_delete_list = []
for i in filtered_list:
if i >= should_delete:
should_delete_list.append(i)
should_delete_list.sort()
print(should_delete_list[0])일단 루트폴더의 크기를 구하기 위해 outermost 라는 딕셔너리를 만들었다.
루트 폴더에 들어있는 것들만 계산되면 되기 때문에 current_path가 0인 경우에 들어가는 폴더, 파일을 outermost라는 딕셔너리에도 들어가게 하였다.
그리고 for 문을 돌며 outermost의 key, value를 받아오고, 파일인 경우에는 바로 used_space에 크기를 더해주고, 폴더인 경우에는 dir_dict에서 outermost의 키를 활용하여 해당 폴더 크기를 받아와 used_space에 더해주었다.
그렇게 해서 적어도 unused space가 30,000,000이 되게 하기 위해 지워져야하는 최소한의 크기를 구해내어 should_delete라는 변수에 담아주고 이를 활용하여 이 크기 이상인 폴더의 크기들을 should_delete_list에 담아준다.
이를 크기별로 나열(sort()) 한 다음 그 중 가장 작은 값 ([0])을 구해낸다.
6일차까지는 큰 어려움 없이 풀었는데 이번에는 너무 복잡했다.
딕셔너리도, 재귀함수도 처음 써보는 거라 개념을 익히고 활용해보는 것이 어려웠다.
그래서 시간은 엄청 오래 걸렸지만 풀려서 기쁘다!