⭐️ LeetCode 알고리즘 풀이 (with Python)

# Simplify Path

[Quetion]

LeetCode 71. Simplify Path

📌 접근법

[문제 이해]

• unix 스타일 절대경로를 표준경로로 변환
• 경로는 / 로 시작
• / 으로 끝나지 않아야 함
• 디렉토리는 / 로 구분되어야 함
• . or ..는 경로에 미포함

stack의 LIFO 특성을 활용하여 디렉토리의 문자열만 Push하고 /를 배치해주는 방법으로 접근했다.

• path 경로를 / 기준으로 분리 (split 함수 사용)
• 분리한 경로 만큼 반복
• 빈 값 or .이면 pass
• ..인 경우 POP
• 이외(디렉토리 문자열)에는 Push
• 스택에 있는 문자열 앞과 문자열 사이에는 / 삽입

💻 구현

class Solution:
    def simplifyPath(self, path: str) -> str:
        # stack
        result=[]
        
        # /로 경로 문자열 분리
        path = path.split('/')
        for i in path:
        	# 빈 값 pass
            if i == '':
                continue
            
            # ..일 경우 POP, stack != None
            elif i == '..':
                if result != []:
                    result.pop()
            
            # . pass, 문자열 PUSH
            elif i != '.':
                result.append(i)
        
        # '/' 삽입 
        return '/'+'/'.join(result)

Runtime: 38ms | Memory: 16.1MB
LeetCode 코드 중 Runtime 76%, Memory 97% 해당하는 결과

📌 로직 핵심

• /로 경로 문자열 분리함으로써 //같은 문자열 PUSH 상황 삭제
• ..일 경우 Stack Underflow 방지를 위해 result가 None이 아닌 상황에만 POP
• '/'.join 연산으로 디렉토리 문자열 사이에 /추가, '/'+'/'로 경로 a/b 앞에 /추가

📝 Simplify Path 회고

• 시간복잡도와 공간복잡도는 모두 O(N)이다.

• 스택의 LIFO 특성을 응용하는 간단한 문제였다. 처음에는 path를 그대로 반복하며 if문과 함께 push와 pop을 진행했다. 하지만 코드가 복잡했고 //이 섞이면서 뜻대로 되지않았다.

• 그래서 /기준으로 문자열을 분리해보았고, if문의 경우의 수도 줄어들며 join 연산을 통해 간편하게 /을 추가 할 수 있어서 문제를 해결할 수 있었다.

• 문제를 해결하고 다른 솔루션들을 보아도 같은 방법으로 접근한 코드들이 많았다는 것을 확인하며 간단한 문제일수록 생각이 비슷하다는 것을 느낄 수 있었다.