문제 개요
문자열 리스트로 표현된 Unix 경로가 주어졌을 때, 이를 정규화된 최종 경로로 변환하는 프로그램을 만들어 보겠습니다. Unix 시스템에서 ..는 한 단계 위(상위) 디렉터리로 이동한다는 의미이고, .는 현재 디렉터리에 머무른다는 의미입니다. 따라서 경로 정규화란 이 두 기호를 모두 처리하여 실제로 도달하게 되는 최종 디렉터리를 계산하는 과정을 말합니다.
예를 들어 입력이 다음과 같다고 가정해 보겠습니다.
["usr", "..", "usr", ".", "local", "etc", "foo"]
이 경로를 문자열로 연결하면 "/usr/../usr/./local/etc/foo"와 같으며, 정규화하면 "/usr/local/etc/foo"가 됩니다. 따라서 기대하는 출력은 다음과 같습니다.
['usr', 'local', 'etc', 'foo']
접근 방법: 스택(Stack) 활용
이 문제는 스택 자료구조를 사용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 디렉터리를 순서대로 쌓아 올리고, ..를 만날 때마다 마지막 요소를 제거하는 것입니다. 알고리즘은 다음과 같습니다.
- 결과를 저장할 빈 리스트 s를 생성합니다.
- 경로의 각 요소 i에 대해 다음을 반복합니다.
- i가 '..'인 경우: s가 비어 있지 않다면 마지막 요소를 제거합니다(상위 디렉터리로 이동).
- i가 '.'이 아닌 경우: i를 s의 끝에 추가합니다.
- i가 '.'인 경우: 아무 작업도 하지 않습니다(현재 디렉터리 유지).
- 모든 요소를 처리한 후 s를 반환합니다.
Python 구현 예제
class Solution:
def solve(self, path):
s = []
for i in path:
if i == '..':
if len(s) > 0:
s.pop()
elif i != '.':
s.append(i)
return s
ob = Solution()
print(ob.solve(["usr", "..", "usr", ".", "local", "etc", "foo"]))
입력
["usr", "..", "usr", ".", "local", "etc", "foo"]
출력
['usr', 'local', 'etc', 'foo']
단계별 동작 원리
코드가 어떻게 동작하는지 입력 예제를 기준으로 스택의 변화를 추적해 보겠습니다.
- "usr" → ['usr'] (일반 디렉터리이므로 추가)
- ".." → [] (마지막 요소 'usr' 제거)
- "usr" → ['usr'] (다시 추가)
- "." → ['usr'] (현재 디렉터리이므로 변화 없음)
- "local" → ['usr', 'local']
- "etc" → ['usr', 'local', 'etc']
- "foo" → ['usr', 'local', 'etc', 'foo']
최종적으로 스택에 남아 있는 요소들이 곧 정규화된 경로의 각 디렉터리가 됩니다.
시간 복잡도 분석
이 알고리즘은 경로의 각 요소를 정확히 한 번씩만 처리하므로 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 결과를 저장하는 리스트 크기에 비례하여 O(n)입니다. 스택의 push와 pop 연산이 모두 O(1)이기 때문에 매우 효율적입니다.