(Leetcode) 49 - Group Anagrams
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
https://leetcode.com/problems/group-anagrams/description/
지난번에도 anagram 과 관련된 문제를 풀었던 적이 있다. anagram은 같은 글자를 사용해 조합만 바뀐 형태를 의미한다.
(Leetcode) 242 - Valid Anagram
내가 작성한 풀이
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> result = new ArrayList<>();
HashMap<String, Integer> map = new HashMap<>();
for (String str : strs) {
char[] temp = str.toCharArray();
Arrays.sort(temp);
String sorted = String.valueOf(temp);
if (map.containsKey(sorted)) {
result.get(map.get(sorted)).add(str);
} else {
int newIndex = result.size();
List<String> newArrayList = new ArrayList<>();
result.add(newArrayList);
newArrayList.add(str);
map.put(sorted, newIndex);
}
}
return result;
}
TC, SC
시간 복잡도는 O(n * m log m)이고, 공간 복잡도는 O(n * m)이다. 여기서 m은 str 배열(strs)의 각 str의 평균이다.
조금 더 고려해볼 부분
문자열은 입력값 strs 으로 이미 메모리에 올라와 있는 상태일 것이다. 실제로는 모든 문자열을 메모리에 다시 입력하는 것이 아니라 참조변수로 사용할 것이기 때문에 O(n)에 가까울 수 있다.