[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일차까지는 큰 어려움 없이 풀었는데 이번에는 너무 복잡했다. 

딕셔너리도, 재귀함수도 처음 써보는 거라 개념을 익히고 활용해보는 것이 어려웠다. 

그래서 시간은 엄청 오래 걸렸지만 풀려서 기쁘다!