문제는 여기에서 볼 수 있다.
문제
일단 Anagram(아나그램)이 무엇인지 알아야 한다.
어떠한 단어나 구(phrase)를 이루고 있는 글자(알파벳)를
정확히 한 번씩만 사용해서 만든
다른 단어나 구를 아나그램이라고 한다.
예를 들면, "eat"으로는 "tea",
혹은 "tree"로는 "reet"와 같은 아나그램을 만들 수 있다.
이 문제에서는 여러 문자열을 담은 리스트가 입력으로 주어지고
그 문자열들을 아나그램끼리 모아서 return 하면 된다.
풀이
첫 번째 방법
처음에는 입력받은 리스트의 원소를 순회하며
각 원소를 sorting 하고 해당 값을 Dictionay의 key 값으로 사용하여
value에는 리스트의 원소를 넣을 생각이었지만,
시간 복잡도가 꽤 걸릴 것 같아 시도하지 않았다.
그런데 아무리 생각해도 다른 풀이는 안 떠올라서
Solution을 보니 위에서 언급한 내 풀이가
토씨 하나 안 틀리고 첫 번째 솔루션으로 있었다 ㄷ ㄷ;;
리스트의 길이를 N, 가장 긴 문자열의 길이를 K라고 할 때,
시간 복잡도는 O(NKlogK) 이다.
(N은 리스트 순회 시간, KlogK는 sorting 시간)
두 번째 방법
Solution에는 두 번째 방법까지 있었는데,
리스트의 각 원소(문자열)를 이루고 있는 알파벳을 세어
해당 값을 key 값으로 이용하는 방법이다.
놀랍게도, collections 라이브러리의 Counter 메서드를 사용하여
구현해보려고 했던 방법과 또다시 일치했다 ㄷ ㄷ;
Solution에서는 조금 다른 방식을 사용했는데,
"tree"을 예로 들면,
"tree"을 이루고 있는 알파벳을 counting 하고
0으로 초기화된 알파벳의 개수(26개)와 같은 길이의 리스트를 만든 후,
(0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0)
위처럼 counting 한 알파벳의 인덱스의 값을 1씩 더해 key 값으로 사용한다.
이 방법의 시간 복잡도는 O(NK)이다.
(N은 리스트 순회 시간, K는 counting 시간)
성능
시간 복잡도만 보면 두 번째 방법이 더 빨라야 하는데
실행시켜보면 첫 번째 방법이 압도적으로 빠르다.
솔직히 이유는 정확히 모르겠지만,
추측해보자면
두 번째 방법은 0으로 초기화된 리스트를 매번 만들고
counting 할 때도 + 연산이 매번 들어가기 때문이지 않을까 싶다.
끝!
'Study > Algorithm Coding' 카테고리의 다른 글
[Algorithm][LeetCode][Medium][Python] 55. Jump Game (0) | 2021.04.24 |
---|---|
[Algorithm][LeetCode][Easy][Python] 53. Maximum Subarray (0) | 2021.04.18 |
[Algorithm][LeetCode][Medium][Python] 48. Rotate Image (0) | 2021.03.07 |
[Algorithm][LeetCode][Medium][Python] 46. Permutations (0) | 2021.02.20 |
[Algorithm][LeetCode][Hard][Python] 42. Trapping Rain Water (0) | 2021.02.15 |