[코딩테스트] 폴더 검사하기 문제

문제

[자식폴더, 부모폴더]의 폴더구조에 대한 리스트 folders, 
[파일이름, 파일크기, 속한폴더이름]의 파일 속성에 대한 리스트 files, 
확인할 폴더 목록을 담은 리스트 selected, 
확인하지 않을 파일 목록을 담은 리스트 excepted
이렇게 네 개의 파라미터가 주어질 때, 

확인할 파일들에 대해 
[확인해야 할 파일의 크기(단위 제외), 파일 개수] 의 형태로 반환하시오. 
단, 파일 크기는 B 단위로 변환되어야 합니다.

예시 1)
folders = [['animal', 'root'], ['fruit', 'root']]
files = [['cat', '1B', 'animal'], ['dog', '2B', 'animal'], ['apple', '4B', 'fruit']]
selected = ['animal']
excepted = ['apple']
정답: [3, 2]

예시 2)
folders = [['food', 'root'], ['meat', 'food'], ['fruit', 'food'], ['animal', 'root']]
files = [['cat', '1B', 'animal'], ['dog', '2B', 'animal'], 
         ['fork', '1KB', 'meat'], ['beef', '8KB', 'meat'], 
         ['apple', '4B', 'fruit'], ['fire', '83B', 'root']]
selected = ['root', 'meat']
excepted = ['fork', 'apple']
정답: [8278, 4]

 

풀이

1. folders로 root 폴더를 root 노드로 갖는 그래프 만들기
2. 그래프를 참고해 selected에 속한 폴더의 하위 폴더들을 모두 포함하는 selected 재구성
3. 재구성한 selected를 돌며 해당 폴더에 속한 파일들을 확인
4. 확인하는 과정에서 excepted에 속한 파일은 제외, 제외되지 않은 파일들의 용량, 개수 종합
5. KB는 B로 변환 후 B 떼기. [용량, 크기] 형태로 결과 리턴

 

코드

# 1
def make_graph(folders):
  graph = {}
  for folder in folders:
    if folder[1] not in graph:
      graph[folder[1]] = [folder[0]]
    else:
      graph[folder[1]].append(folder[0])
  return graph

# 5
def convert_to_num(size):
  if 'KB' in size:
    return int(size[:-2]) * 1024
  else:
    return int(size[:-1])

# 3~4
def file_check(files, selected, excepted):
  size = 0
  count = 0
  for file in files:
    if file[2] in selected and file[0] not in excepted:
      size += convert_to_num(file[1])
      count += 1
  return [size, count]

def solution(folders, files, selected, excepted):
  # graph = make_graph(folders)

  return file_check(files, selected, excepted)

 

시도

여기서 난 2번을 제외한 함수를 모두 만들었지만 

2번 함수가 제일 핵심이라 문제를 풀지 못했었다..

 

2번 함수를 표현하기 위해 굉장히 다양한 시도를 했는데

 

일반적인 DFS

selected에 속한 폴더를 찾아도 해당 폴더에 속한 폴더들과

밑에를 찍고 나와서 속하지 않은 폴더들을 구분하는 딱 그 시점을 어떻게 찾을지가 애매했다.

순열 또는 조합 DFS

레벨을 두고 해당 레벨의 폴더가 selected에 포함되면 그 밑의 레벨의 폴더들을 selected에 포함시켜볼까 했지만

밑의 레벨을 포함시킬 경우 해당 폴더에 속하지 않은 폴더들까지 영향이 갈 수 있다는 부분이 걸림

 

리뷰

문제를 접하고부터 며칠 후, 풀이 2번에 해당하는 방법을 찾을 수 있었다.

내가 생각했던거와는 달리 DFS의 형태를 띄는 재귀 함수를 통해서 원하는 함수를 만들어낼 수 있었는데

해당 코드는 다음과 같다.

 

코드

def find_subfolders(graph, selected):
  subfolders = []
  def find_recursive(folder):
    subfolders.append(folder)
    if folder in graph:  # 하위 폴더가 없다면 해당 폴더 추가한 것으로 끝
      for subfolder in graph[folder]:
        find_recursive(subfolder)

  for folder in selected:
    find_recursive(folder)
    
  return list(set(subfolders))

selected에 포함된 폴더를 집어넣고

재귀를 이용한 DFS 알고리즘을 통해 모두 subfolders에 추가한다.

 

DFS를 배울 때, 스택과 큐를 이용해서 구현하는 방법만 배웠기 때문에

재귀를 이용해서도 구현할 수 있다는 사실을 몰랐던게 내가 이 문제를 어렵게 느꼈던 이유가 아니었을까 싶다..

 

포스팅하면서 보니 find_subfolders 함수에서도 몇가지 개선될 사항이 보여 개선을 해봤다.

1. 하위 폴더를 모두 포함한 후 set을 통해 중복 제거를 하는게 아닌 애초에 subfolders에 넣을 때 없을 때만 넣기
2. subfolders에 해당 폴더가 이미 존재할 경우 하위 폴더들도 모두 존재할테니 
   이후의 재귀 함수 호출을 생략해 연산 줄이기

개선 코드

def find_subfolders(graph, selected):
  subfolders = []
  def find_recursive(folder):
    if folder not in subfolders:  
    # subfolders에 folder가 없을 때만 추가해 중복 방지
    # subfolders에 folder가 존재할 경우 하위 폴더들도 이미 포함된거라 판단
      subfolders.append(folder)
      if folder in graph:  # 하위 폴더가 없다면 해당 폴더 추가한 것으로 끝
        for subfolder in graph[folder]:
          find_recursive(subfolder)

  for folder in selected:
    find_recursive(folder)
  return subfolders

 

정리

위 과정들을 통해 결국 내가 작성해야 했던 코드는 다음과 같다.

 

# 1
def make_graph(folders):
  graph = {}
  for folder in folders:
    if folder[1] not in graph:
      graph[folder[1]] = [folder[0]]
    else:
      graph[folder[1]].append(folder[0])
  return graph
graph = make_graph(folders)
print(graph)

# 5
def convert_to_num(size):
  if 'KB' in size:
    return int(size[:-2]) * 1024
  else:
    return int(size[:-1])
# result = convert_to_num('83B')
# print(result)

# 3~4
def file_check(files, selected, excepted):
  size = 0
  count = 0
  for file in files:
    if file[2] in selected and file[0] not in excepted:
      size += convert_to_num(file[1])
      count += 1
  return [size, count]

# 2
def find_subfolders(graph, selected):
  subfolders = []
  def find_recursive(folder):
    if folder not in subfolders:
      subfolders.append(folder)
      if folder in graph:
        for subfolder in graph[folder]:
          find_recursive(subfolder)
  for folder in selected:
    find_recursive(folder)
  return subfolders

def solution(folders, files, selected, excepted):
  graph = make_graph(folders)
  selected_folders = find_subfolders(graph, selected)
  return file_check(files, selected_folders, excepted)

예시 파라미터들을 대입해본 결과 모두 원하는 결과가 나오는 것을 확인했다.

 

이론적으로만 공부한 상태에서 문제 경험이 많이 없다는게 이 문제를 통해 여실히 드러났는데

위 문제를 머릿속에 새겨놓고 재귀와 DFS, BFS

더 나아가 트리와 그래프를 다루는 능력을 많이 길러

어떤 문제 상황에서도 응용해 사용할 수 있게끔 실력을 갈고 닦아야겠다.