https://programmers.co.kr/learn/courses/30/lessons/17685
-
flow
일단 검색 단어 수 N 이고, 단어들 평균 길이가 M이라고 했을 때, 어떤 알고리즘을 쓰던간에 한번씩 탐색이 필요하니 O(MN) 이 최소일 것이다. 처음에 생각한 아이디어는 단어들을 정렬해서 linear하게 앞글자만 비교해 나아가면 되지 않나 생각했다. (맨 앞글자가 곂치는 단어가 있는 경우 맨 앞글자를 제외하고 다시 리스트에 추가하고 없는 경우에는 제외)
go,gone,guild 인 경우 (1) o,one,uild(answer = 3)(2) ne(answer = 6) (3)answer =7
하지만 반례들이 존재했고, 테스트해본 결과, 다음과 같은 문제가 있었다. go, gone, do, done 인 경우, 첫글자를 뺀 후, o one o one 가 남아서 정답과는 거리가 멀어지게 된다. 그래서 solution을 재귀함수로 만들어주고 앞글자가 일치하는 단어들끼리만 따로 그룹 나눠주면서 함수가 여러번 호출 되게끔 만들어줘야 했다. (계속 sort 해주는 점은 덤으로..)
결과적으로 정렬하는데 O(NlogN) 과 linear한 탐색에서 O(MN) 이 걸리는데 나중에 좀 더 생각해보니 그냥 트리 구조를 이용하는게 낫지 않았나 싶었다.. -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level4/A.17685.py
