명령어 압축

면접 대비

시간 제한2초메모리 제한1024 MB

요약

n개의 절대 경로가 주어질 때, 상대 경로로 나타낸 성분 수의 총합이 최소가 되는 작업 디렉터리를 찾습니다.

난이도: 보통10점 중 5점
유형: 트라이, 트리, 문자열
정답자: 아직 제출이 없습니다

문제

터미널에서 작업하는 당신은 작업 디렉터리를 원하는 디렉터리로 바꿀 수 있다. 작업 디렉터리가 /a/b이면 절대 경로 /a/b/x를 x로 가리킬 수 있다. 상위 디렉터리로 한 단계 올라갈 때는 ..을 쓴다. 예를 들어 /a/y/z는 ../y/z가 되고, /some/other/directory는 ../../some/other/directory가 된다.

명령어에 들어갈 $n$ 개의 절대 경로를 모두 상대 경로로 쓰려고 한다. 상대 경로 구성 요소의 총 개수가 최소가 되도록 작업 디렉터리를 골라라. 예를 들어 a/a/b/c와 ../../a/b는 각각 구성 요소가 4개다. 작업 디렉터리는 디렉터리여야 하며 파일 경로일 수 없다. 같은 디렉터리 안에서 파일 이름이 디렉터리 이름과 겹치는 일은 없다.

입력

첫 줄에 절대 경로의 개수를 나타내는 정수 $n$ ( $1 \leq n \leq 10^5$ )이 주어진다. 이어지는 $n$ 개의 줄에는 절대 경로 $s$ 가 한 줄에 하나씩 주어진다. 각 경로는 소문자 알파벳(a-z)과 슬래시(/)만 포함하며, /로 시작하고 /로 끝나지 않으며, //를 포함하지 않는다. $n$ 개 문자열의 전체 문자 수는 최대 $10^6$ 이다.

출력

작업 디렉터리를 바꿨을 때 얻을 수 있는 상대 경로 구성 요소 개수의 최솟값을 출력한다.

예제3

예제 1

입력

3
/home/jury/compressingcommands/secret
/home/jury/compressingcommands/solutions
/home/hackerman/answers

예상 출력

예제 2

입력

7
/a/b/a/a/b
/a/a/a
/b
/a/a/b
/a/b/a/a/a
/c
/a/b/a/b

예상 출력

예제 3
입력
```
3
/x/y/z
/x/y/z
/x/y/z
```
예상 출력
```
3
```