n개의 문자열로 이루어진 배열 names가 있다고 가정해 보겠습니다. 우리는 파일 시스템에 n개의 디렉터리를 만들어야 하며, i번째 단계에서 names[i]라는 이름의 디렉터리를 생성합니다. 두 파일은 동일한 이름을 가질 수 없기 때문에, 중복된 디렉터리 이름을 입력하면 시스템은 자동으로 이름 뒤에 (k) 형태의 접미사를 붙입니다. 여기서 k는 해당 이름이 고유해지는 가장 작은 양의 정수입니다. 최종적으로 길이가 n인 문자열 배열 ans를 구해야 하며, ans[i]는 i번째 디렉터리가 생성될 때 실제로 할당되는 이름이 됩니다.
예를 들어 입력이 names = ["my_dir","my_dir(1)","my_new_dir","my_new_dir","abc"]라면, 출력은 ['my_dir', 'my_dir(1)', 'my_new_dir', 'my_new_dir(1)', 'abc']가 됩니다. "my_new_dir"이 이미 한 번 등장했기 때문에, 다시 등장한 이름에는 (1)이 붙어 고유성이 유지됩니다.
문제 해결 접근 방식
이 문제는 해시 맵(딕셔너리)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 이름이 몇 번 등장했는지 기록하고, 중복이 발생할 때마다 카운트를 이용해 새로운 후보 이름을 만든 뒤, 그 후보 역시 중복이 아니면 확정하는 것입니다.
dic := 새로운 맵(defaultdict)을 생성하고, 존재하지 않는 키는 기본값 0으로 처리합니다.
res := 결과를 담을 새로운 리스트를 생성합니다.
names의 각 name에 대해 다음을 반복합니다.
name이 dic에 없다면:
dic[name] := dic[name] + 1 로 등장 횟수를 기록합니다.
res의 끝에 name을 그대로 추가합니다.
name이 이미 dic에 있다면:
newname := name + '(' + dic[name] + ')' 형태로 후보 이름을 만듭니다.
newname이 dic에 존재하는 동안 다음을 반복합니다.
dic[name] := dic[name] + 1 로 카운트를 증가시킵니다.
newname을 새로운 후보 이름으로 갱신합니다.
dic[newname] := 1 로 새 이름의 등장을 기록합니다.
res의 끝에 newname을 추가합니다.
모든 처리가 끝나면 res를 반환합니다.
Python 구현 예제
아래 코드를 통해 위 알고리즘이 실제로 어떻게 동작하는지 확인할 수 있습니다.
from collections import defaultdict
def solve(names):
dic = defaultdict(int)
res = []
for name in names:
if name not in dic:
dic[name] += 1
res.append(name)
else:
newname = name +'(' + str(dic[name]) + ')'
while newname in dic:
dic[name] += 1
newname = name +'(' + str(dic[name]) + ')'
dic[newname] = 1
res.append(newname)
return res
names = ["my_dir","my_dir(1)","my_new_dir","my_new_dir","abc"]
print(solve(names))입력
["my_dir","my_dir(1)","my_new_dir","my_new_dir","abc"]
출력
['my_dir', 'my_dir(1)', 'my_new_dir', 'my_new_dir(1)', 'abc']
정리
이 알고리즘은 collections.defaultdict를 사용해 각 이름의 등장 횟수를 추적함으로써, 중복 이름이 나타날 때마다 (k) 접미사를 붙여 고유한 이름을 보장합니다. while 루프를 통해 후보 이름까지 겹치는 경우도 모두 처리할 수 있으므로, "my_dir", "my_dir(1)"처럼 이미 접미사가 붙은 이름이 미리 존재하는 경우에도 올바르게 동작합니다. 시간 복잡도는 일반적으로 O(n × m) 수준(m은 평균 접미사 탐색 횟수)으로, 실무적인 파일명 충돌 처리 로직에 널리 응용할 수 있습니다.