두 가지 핵심 기능을 제공하는 파일 시스템을 설계해야 한다고 가정해 보겠습니다.
- createPath(path, value) — 새로운 경로를 생성하고 가능한 경우 해당 경로에 값을 연결한 뒤 True를 반환합니다. 경로가 이미 존재하거나 부모 경로가 존재하지 않으면 False를 반환합니다.
- get(path) — 주어진 경로에 연결된 값을 조회하여 반환하며, 경로가 존재하지 않으면 -1을 반환합니다.
경로 형식 이해하기
경로는 슬래시(/) 뒤에 하나 이상의 영문 소문자가 이어지는 문자열이 하나 이상 연결된 형태입니다. 예를 들어 /programming과 /programming/problems는 유효한 경로이지만, 빈 문자열과 /는 유효하지 않습니다.
동작 예시를 살펴보겠습니다. 파일 시스템 객체를 생성한 후 createPath('/a', 1)로 경로를 만들면, 이후 get('/a')를 호출했을 때 출력값은 1이 됩니다.
풀이 접근 방법
이 문제는 트라이(Trie) 자료구조와 유사하게 중첩 딕셔너리(맵)를 활용하면 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- 맵(딕셔너리) d를 정의합니다.
- createPath 메서드는 path와 value를 인자로 받으며 다음과 같이 동작합니다.
- p := path를 '/'로 분할한 컴포넌트 리스트
- x := d
- i를 1부터 len(p) - 1까지 반복:
- p[i]가 x에 없으면 False를 반환
- x := x[p[i]][1]
- p의 마지막 요소가 이미 x에 존재하면 False를 반환
- x[마지막 요소] := [v, 빈 맵] 형태로 저장
- True를 반환
- get 메서드는 path를 인자로 받으며 다음과 같이 동작합니다.
- x := d
- p := path를 '/'로 분할한 컴포넌트 리스트
- i를 1부터 len(p) - 1까지 반복:
- p[i]가 x에 없으면 -1을 반환
- x := x[p[i]][1]
- p의 마지막 요소가 x에 존재하면 x[마지막 요소][0]을 반환하고, 그렇지 않으면 -1을 반환
파이썬 구현 예제
다음 구현 코드를 통해 더 자세히 이해해 보겠습니다.
class FileSystem(object):
def __init__(self):
self.d = {}
def create(self, p, v):
p = p.split("/")
x = self.d
for i in range(1,len(p)-1):
if p[i] not in x:
return False
x = x[p[i]][1]
if p[-1] in x:
return False
x[p[-1]] = [v,{}]
return True
def get(self, p):
x = self.d
p = p.split("/")
for i in range(1,len(p)-1):
if p[i] not in x:
return -1
x= x[p[i]][1]
if p[-1] in x:
return x[p[-1]][0]
else:
return -1
ob = FileSystem()
print(ob.create("/a", 1))
print(ob.get("/a"))입력
객체를 초기화한 후 createPath("/a", 1)과 get("/a")를 호출출력
True 1