[BOJ] 5052번: Phone List

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

맨 처음에 떠올린건 트리를 이용한 O(n) 풀이였습니다. 예를 들어 입력이 

113

12340

123440

12345

98346

인 경우

뭐 대충 이런식으로 생긴 그래프를 그리고 Leaf에 따로 표식을 남겨서 새로운 수를 입력할 때 Leaf를 지나거나,(이 경우 새로운 수가 이전의 수의 prefix가 됨) 새로운 수를 입력할 때 새로운 트리의 원소를 생성하지 않고 끝날 때(이 경우 새로운 수가 이전의 수의 prefix가 됨) 문제가 생김을 알 수 있습니다.

그런데 구현하기가 조금 껄끄러워 다른 방법이 없을까 고민을 하다가 좋은 방법이 떠올랐는데, 애초에 그냥 사전순으로 정렬을 하고 나면 인접한 원소에 대해서만 확인을 해주면 됨을 알 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/5052.cpp