문제
문제 해설
전형적인 트라이 문제이나, 트라이 알고리즘을 구현하지 않아도 풀 수 있는 문제입니다.
(Trie)input이 주어지면 그것을 문자열을 저장하는 트리의 형태로 변경 후 dfs탐색을 이용하여 해결할 수 있습니다.
또 다른 풀이는, 주어진 String들을 전부 리스트의 형태로 저장한 뒤, 정렬을 이용하는 방법입니다. 리스트들을 하나씩 돌며 정렬된 형태의 2차원 리스트이기 때문에 바로 전 리스트와 비교하면 공통 노드의 깊이를 알 수 있습니다.
["1","2","4"], ["1","2","3","4"] 이렇게 두 문자열 리스트가 있다면 공통 depth는 2입니다.
그리고 예외 처리가 중요한데, 전 리스트와 비교할 수 없는 상황일 경우(현재 첫번째 리스트, 전 리스트의 인덱스를 참조할 수 없음)와 공통 부분이 발견되지 않는 즉시, flag를 놓아 더이상 전 리스트와 비교하지 않고 바로 출력되게 해주시면 됩니다.
풀이 코드
import sys
input = sys.stdin.readline
n = int(input())
arr = []
for i in range(n):
arr.append(list(map(str, input().rstrip().split()))[1:])
# 요구사항을 맞추고, 전 배열과 비교하기 위함
arr.sort()
for i in range(n):
flag = False # 공통된 줄기가 끝나면 True
for j in range(len(arr[i])):
# 현재 element와 전 리스트를 비교할 수 없는 경우
if flag or i == 0 or len(arr[i - 1]) <= j:
print("--" * j + arr[i][j])
# 공통된 줄기가 어디 까지인지 체크
elif not flag and arr[i - 1][j] != arr[i][j]:
flag = True
print("--" * j + arr[i][j])