Python으로 폴더 이동 로그에서 홈 디렉터리까지 필요한 최소 이동 횟수 찾기

폴더에 진입하는 경로가 담긴 로그(logs) 목록이 있다고 가정해 보겠습니다. 각 로그 항목은 다음 세 가지 기호 중 하나를 나타냅니다.

• "../" : 현재 폴더에서 상위(부모) 폴더로 이동합니다. 이미 메인 폴더에 있다면 위치는 그대로 유지됩니다.

• "./" : 현재 폴더에 그대로 머뭅니다.

• "x/" : 이름이 x인 하위(자식) 폴더로 이동합니다.

문제의 목표는 주어진 로그를 순서대로 실행한 뒤, 마지막으로 도착한 폴더에서 메인(홈) 폴더로 돌아가기 위해 필요한 최소 연산 횟수를 구하는 것입니다.

예를 들어 입력이 logs = ["Dir1/","Dir2/","../","Dir2/","Dir3/","./"]라면 출력은 3이 됩니다.

위 그림에서 확인할 수 있듯이, 마지막 위치에서 홈으로 돌아가려면 세 번 뒤로 물러나야 합니다.

접근 방법

이 문제는 스택(stack) 자료구조를 활용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 현재 깊이를 스택으로 추적하고, 최종적으로 스택에 남은 요소 개수가 곧 되돌아가야 할 단계 수라는 점입니다. 단계별 절차는 다음과 같습니다.

• stk := 새로운 빈 리스트를 생성합니다.

• logs의 각 항목 i에 대해 다음을 반복합니다.

  • i가 "../"와 같고 stk의 크기가 0보다 크면, stk에서 마지막 요소를 제거합니다.

  • 그렇지 않고 i가 "./"도 아니고 "../"도 아니라면, i를 stk의 끝에 추가합니다.

  • 그 외의 경우("./")에는 아무 작업 없이 다음 반복으로 넘어갑니다.

• 마지막으로 stk에 남아 있는 요소 개수를 반환합니다. 이 값이 홈으로 돌아가는 데 필요한 최소 연산 횟수입니다.

예제 (Python)

다음 구현을 통해 더 자세히 이해해 보겠습니다.

def solve(logs):
    stk = []
    for i in logs:
        if i == "../" and len(stk) > 0:
            stk.pop()
        elif i != "./" and i != "../":
            stk.append(i)
        else:
            continue
    return len(stk)

logs = ["Dir1/","Dir2/","../","Dir2/","Dir3/","./"]
print(solve(logs))

입력

["Dir1/","Dir2/","../","Dir2/","Dir3/","./"]

출력

3

동작 원리 살펴보기

각 로그 항목이 처리될 때 스택의 변화를 단계별로 살펴보면 다음과 같습니다.

• "Dir1/" → 스택에 추가 → [Dir1]

• "Dir2/" → 스택에 추가 → [Dir1, Dir2]

• "../" → 마지막 요소 제거 → [Dir1]

• "Dir2/" → 스택에 추가 → [Dir1, Dir2]

• "Dir3/" → 스택에 추가 → [Dir1, Dir2, Dir3]

• "./" → 위치 변화 없음 → [Dir1, Dir2, Dir3]

최종적으로 스택에 3개의 폴더가 남아 있으므로, 홈으로 돌아가려면 정확히 3번의 "../" 연산이 필요합니다.

복잡도 분석

시간 복잡도는 로그를 한 번만 순회하므로 O(n)이며, 공간 복잡도는 최악의 경우 모든 폴더가 스택에 쌓일 수 있으므로 O(n)입니다.