엔지니어가 5개 알고리즘 문제를 풀면서 구간 교집합, 스택 기반 경로 정규화, 보조 스택을 활용한 상수 시간 최소값 조회 패턴 습득

Context

구간 겹침 문제에서 기존 코드를 수정하려 했으나 정확성이 낮았다. 경로 정규화에서 split() 함수의 동작을 처음에는 이해하지 못했다. Min Stack을 min heap으로 접근했으나 실제 문제의 요구사항과 맞지 않았다.

Technical Solution

• 풍선 격추 문제: 구간을 끝점 기준으로 정렬한 후 첫 번째 풍선의 끝점에 화살을 발사하고, 이후 구간이 화살의 범위를 벗어나면 새 화살을 추가하는 탐욕 알고리즘 적용
• 경로 정규화: split("/")으로 경로 구성요소를 분해하고 스택에 저장하되, ".."은 스택에서 pop, "."과 빈 문자열은 무시하는 방식으로 처리
• Min Stack: 데이터를 저장하는 주 스택과 최소값만 기록하는 보조 스택 2개를 병렬로 관리하여 모든 연산을 O(1)에 수행
• 경로 정규화 join 연산: "/".join()은 선행 및 후행 슬래시를 추가하지 않으므로 앞에 "/"를 붙여 절대 경로 형식 보장
• 연결 리스트 순환 감지: 느린 포인터는 1칸, 빠른 포인터는 2칸씩 이동하되, 빠른 포인터의 존재 여부를 사전에 검증하여 널 참조 에러 방지

Key Takeaway

구간 문제는 끝점 기준 정렬 후 탐욕 선택으로 최소 자원을 찾고, 스택 보조 자료구조는 상수 시간 특수 조회를 구현하는 핵심 패턴이다.