https://leetcode.com/problems/group-anagrams/
Group Anagrams - LeetCode
Can you solve this real interview question? 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
leetcode.com
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 exactly once.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
Constraints:
- 1 <= strs.length <= 10^4
- 0 <= strs[i].length <= 100
- strs[i] consists of lowercase English letters
풀이방법
입력값(str)의 길이가 10^4이니까, 시간복잡도는 O(n), O(nlogn)정도로 생각했다. 즉, for문 하나에, if문 정도.??
알고리즘이 익숙하지 않은 나에게, 이정도가 최선의 접근이다.
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for(String s : strs) {
// 키를 정렬 후 String 형태로 다시 변환
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = String.valueOf(chars);
// 만약 key가 없으면 map key 추가, 있으면 value에 add
if(!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
map.get(key).add(s);
}
return new ArrayList<>(map.values());
}
}
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| [알고리즘 - 백준] 11724번 연결 요소의 개수 JAVA (0) | 2024.08.09 |
|---|---|
| [알고리즘 - 백준] 1260번 DFS와 BFS (0) | 2024.08.09 |
| [ArrayList를 Array로 형 변환] - 코딩테스트 출력값이 안 맞을 때 (0) | 2024.02.03 |
| [for each 문] - 알고리즘 공부하다 알게 된 신기한 것 (0) | 2024.02.01 |
| 백준 (10811) - 바구니 뒤집기 Java (0) | 2023.09.08 |
