[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

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 1063번: 킹  (0) 2018.01.31
[BOJ] 9536번: What does the fox say?  (0) 2018.01.31
[BOJ] 14889번: 스타트와 링크  (0) 2018.01.29
[BOJ] 4354번: Power Strings  (0) 2018.01.27
[BOJ] 1701번: Editor  (0) 2018.01.24
[BOJ] 3111번: CENZURA  (0) 2018.01.22
  Comments
댓글 쓰기