프로젝트 구조를 화면에 출력할 때, 실제 트리 대신 문자열 하나로 저장하는 경우가 있습니다.
각 줄은 하나의 폴더나 문서를 의미하고, 앞에 붙은 탭 문자의 개수는 깊이를 나타냅니다.
이때 모든 문서 경로 중에서 가장 긴 전체 경로 길이를 구해야 하는 문제가 있습니다.
겉으로 보면 문자열 문제처럼 보이지만, 실제로는 깊이별 누적 길이 관리가 핵심입니다.
문제
한 협업 도구가 프로젝트 구조를 아래처럼 문자열 하나로 내보낸다고 가정해보겠습니다.
workspace
guides
intro.md
src
api
handlers.py
ui
button.tsx
이 구조는 다음과 같이 볼 수 있습니다.
workspace
├── guides
│ └── intro.md
└── src
├── api
│ └── handlers.py
└── ui
└── button.tsx
문서 경로는 /로 이어 붙인다고 하겠습니다.
예를 들면 가능한 경로는 다음과 같습니다.
workspace/guides/intro.md
workspace/src/api/handlers.py
workspace/src/ui/button.tsx
이 중 가장 긴 경로의 문자 길이를 반환하면 됩니다.
문서가 하나도 없다면 0을 반환합니다.
조건
\n은 다음 항목을 의미합니다.\t의 개수는 현재 항목의 깊이를 의미합니다.- 이름에
.이 포함되어 있으면 문서로 봅니다. - 폴더 이름에는
.이 들어가지 않는다고 가정합니다. - 경로는
/로 이어 붙입니다.
처음 떠오르는 생각
처음에는 실제 트리를 만들어야 할 것처럼 보일 수 있습니다.
하지만 이 문제에서 정말 필요한 것은 트리 자체가 아닙니다.
우리가 알고 싶은 것은 결국:
현재 깊이까지의 누적 경로 길이
입니다.
예를 들어 아래처럼 내려간다고 해보겠습니다.
workspace
src
api
handlers.py
이때 필요한 정보는 이런 식입니다.
깊이 0까지 길이
깊이 1까지 길이
깊이 2까지 길이
깊이 3에서 문서를 붙였을 때 최종 길이
즉, 전체 구조를 노드로 만들기보다 깊이별 경로 길이만 기억하면 충분합니다.
핵심 아이디어
각 깊이에서 부모 경로까지의 길이를 저장합니다.
path_length = {0: 0}
여기서 path_length[depth]는 현재 항목이 오기 전, 그 깊이의 부모 경로 길이입니다.
줄을 하나씩 읽으면서 다음을 처리하면 됩니다.
- 탭 개수로 현재 깊이를 구한다.
- 탭을 제거해 실제 이름을 구한다.
- 부모 경로 길이에 현재 이름 길이를 더한다.
- 문서면 정답 후보를 갱신한다.
- 폴더면 다음 깊이에서 쓸 길이를 저장한다.
코드
def longest_document_path(structure: str) -> int:
max_length = 0
path_length = {0: 0}
for line in structure.split("\n"):
depth = line.count("\t")
name = line.lstrip("\t")
current_length = path_length[depth] + len(name)
if "." in name:
max_length = max(max_length, current_length)
else:
path_length[depth + 1] = current_length + 1
return max_length
코드 해설
1. 깊이별 누적 길이 저장
path_length = {0: 0}
아직 아무 경로도 없으므로 깊이 0의 시작 길이는 0입니다.
이 딕셔너리는 각 깊이에서 부모 경로까지의 길이를 저장합니다.
2. 줄 단위로 구조 읽기
for line in structure.split("\n"):
각 줄은 하나의 폴더 또는 문서를 의미합니다.
따라서 줄바꿈 기준으로 쪼개서 한 줄씩 처리하면 됩니다.
3. 현재 깊이 계산
depth = line.count("\t")
앞에 붙은 탭 수가 깊이입니다.
예를 들면:
workspace -> 깊이 0
src -> 깊이 1
api -> 깊이 2
handlers.py -> 깊이 3
4. 실제 이름만 꺼내기
name = line.lstrip("\t")
탭은 구조를 표현하기 위한 표시일 뿐 실제 이름은 아닙니다.
그래서 왼쪽 탭을 제거한 문자열만 사용합니다.
5. 현재 위치까지 길이 계산
current_length = path_length[depth] + len(name)
현재 길이는:
부모 경로 길이 + 현재 이름 길이
입니다.
예를 들어 workspace/src/api까지 왔다면, workspace/src/의 길이에 api 길이를 더하면 됩니다.
6. 문서면 최댓값 갱신
if "." in name:
max_length = max(max_length, current_length)
문서만 최종 경로가 될 수 있으므로, .이 있으면 문서로 보고 최댓값 후보를 갱신합니다.
폴더는 정답 후보가 아닙니다.
7. 폴더면 다음 깊이 준비
path_length[depth + 1] = current_length + 1
폴더 아래에는 하위 폴더나 문서가 더 올 수 있습니다.
그래서 다음 깊이에서 쓸 부모 길이를 저장합니다.
여기서 + 1은 / 문자 때문입니다.
예를 들어:
workspace/src/
처럼 다음 이름 앞에 /가 하나 더 들어가기 때문입니다.
실행 예시
structure = (
"workspace\n"
"\tguides\n"
"\t\tintro.md\n"
"\tsrc\n"
"\t\tapi\n"
"\t\t\thandlers.py\n"
"\t\tui\n"
"\t\t\tbutton.tsx"
)
print(longest_document_path(structure))
가장 긴 경로는 다음입니다.
workspace/src/api/handlers.py
이 경로의 문자 길이가 반환됩니다.
복잡도
문자열 전체 길이를 N, 최대 깊이를 D라고 하면:
| 구분 | 복잡도 |
|---|---|
| 시간 복잡도 | O(N) |
| 공간 복잡도 | O(D) |
문자열을 한 번 훑으므로 시간은 O(N)입니다.
추가 공간은 깊이별 누적 길이만 저장하므로 최대 깊이에 비례합니다.
이 문제에서 중요한 관점
이 문제는 “트리를 만들어야 하나?”라는 생각에 먼저 빠지기 쉽습니다.
하지만 실제 핵심은 트리 생성이 아니라:
현재 깊이까지의 누적 길이를 어떻게 관리할까?
입니다.
즉, 문자열을 읽으면서 깊이를 파악하고, 깊이별 길이를 갱신하는 방식으로 풀면 됩니다.
헷갈리기 쉬운 부분
1. 파일과 폴더를 어떻게 구분할까?
이 문제에서는 이름에 .이 있으면 문서라고 가정합니다.
즉:
intro.md -> 문서
src -> 폴더
처럼 처리하면 됩니다.
2. 왜 / 길이를 따로 더할까?
폴더 아래의 하위 경로를 만들 때는 중간에 /가 들어갑니다.
그래서 폴더 길이를 저장할 때는:
current_length + 1
로 다음 깊이를 준비해야 합니다.
3. 왜 스택 문제처럼 보일까?
깊이가 바뀔 때마다 “현재 어느 부모 아래에 있는가”를 따라가야 하기 때문입니다.
실제로 이 문제는 스택을 써도 풀 수 있고, 여기서는 그 아이디어를 깊이별 길이 딕셔너리로 단순화한 것입니다.
정리
이 문제는 문자열 하나로 표현된 들여쓰기 구조를 읽으면서, 가장 긴 문서 경로 길이를 구하는 문제입니다.
핵심은 실제 트리를 만들지 않고:
깊이별 누적 경로 길이만 저장하는 것
입니다.
정리하면 흐름은 다음과 같습니다.
탭 개수로 깊이 계산
-> 부모 경로 길이 확인
-> 현재 이름 길이 더하기
-> 문서면 최댓값 갱신
-> 폴더면 다음 깊이 길이 저장
문자열 문제처럼 보여도, 실제로는 깊이 관리와 누적 정보 갱신이 핵심인 문제입니다.