Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
https://leetcode.com/problems/group-anagrams/description/
Group Anagrams - LeetCode
Group Anagrams - Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters e
leetcode.com
풀이
난이도: Medium
일단 브루트 포스 방식은 적절해 보이지 않는다.
단어를 문자 하나하나 비교하는 것은 N^2의 복잡도로 비효율적이다.
애너그램에서 중요한 것은 단어에 서로 같은 문자가 같은 개수만큼 들어 있는지 이다.
예를 들어 atn와 nat 의 비교 시, 두 단어를 문자 순으로 정렬하면 ant로 동일해진다.
따라서 문자를 정렬해버리고 서로 같은지 비교하면 정렬에 드는 N * logN의 복잡도로 비교가 가능하다.
단어끼리의 비교를 최적화 했다면, 이제 여러 개의 단어를 서로 비교해 그룹을 만드는 문제만 남았다.
사실 이 또한, 이미 단어를 문자 순으로 정렬했다면, 이번에는 단어 List를 오름차순으로 정렬해 버리자.
이러면 같은 단어라면 반드시 해당 단어의 다음에 등장하게 된다.
예를 들어 문제의 예제에, 위의 두가지 정렬을 진행하면, 아래와 같은 순서로 정렬된다.
abt(bat), aet(ate), aet(eat), aet(tea), ant(nat), ant(tan)
즉, 두 정렬을 이용하면 순서대로 그룹화가 끝나게 된다.
해당 알고리즘의 복잡도를 계산해 보자.
단어 List의 길이는 M, 각 단어의 길이를 N이라고 하면, O(M*N*logN)이다.
이외에도 HashMap을 이용한 O(MN) 방식도 있지만, 살짝 기괴하므로 링크만 남긴다.
https://leetcode.com/problems/group-anagrams/solutions/127405/group-anagrams/
코드
구현에서 정렬 시 기존의 단어 형태가 사라지므로 pair <string, string>으로 key, value형태로 기존의 단어를 저장했다.
따라서 key, value 형태를 가지는 Map 자료구조로 대체할 수 있다.
'알고리즘 공부 > LeetCode' 카테고리의 다른 글
| [LeetCode] 124. Binary Tree Maximum Path Sum (C++) (0) | 2022.12.28 |
|---|---|
| [LeetCode] 5. Longest Palindromic Substring (C++) (0) | 2022.12.27 |
| [LeetCode] 76. Minimum Window Substring (C++) (0) | 2022.12.10 |
| [LeetCode] 424. Longest Repeating Character Replacement (c++, 슬라이딩 윈도우) (2) | 2022.09.03 |
| [LeetCode] 3. Longest Substring Without Repeating Characters (c++) (0) | 2022.09.02 |