[Python]문자열 알고리즘1 백준 14725

 문제

 https://www.acmicpc.net/problem/14725

트라이 구조이다.

먼저 아래 사이트를 참고하였다.

https://www.crocus.co.kr/1053

트라이를 생성해두면,  원하는 단어(원소)를 찾을 때 O(m)의 시간만에 찾아 낼 수 있게

 된다.

단점은 공간 복잡도 이며 포인터 크기 * 포인터 배열 개수 * 트라이에 존재하는 총 노드의

 개수 만큼의 메모리가 사용된다.

이번 문제는 출력의 순서를 고려하여 트라이 구조를 통해 풀지는 않았다.

입력값을 배열에 넣어 정렬해 준뒤 차례대로 출력하는데 이전 배열값과 비교하여 같은

것이 있다면 넘어가고 다르다면 --를 붙여 출력하였다.

N=int(input())
ant=[]
 
for i in range(N):
    arr=list(input().split())
    ant.append(arr[1:])
 
ant.sort()
for i in range(N):
    if i==0:#첫배열
        for j in range(len(ant[i])):
            print("--"*j+ant[i][j])
    else:
        count=-1
        for j in range(len(ant[i])):#dfs
            if len(ant[i-1])<=j or ant[i-1][j]!=ant[i][j]: #이전배열과 같은지 비교
                break
            else:#같다면 출력하지 않고 넘어간다.
                count=j#어디까지 같은지 저장
        for j in range(count+1,len(ant[i])):#같은것을 제외한 나머지 인자 출력
            print("--" * j + ant[i][j])