반응형
https://leetcode.com/problems/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 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());
}
}
반응형
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[알고리즘 - 프로그래머스 고득점 Kit] 기능개발 Java (1) | 2024.03.14 |
---|---|
[알고리즘 - 프로그래머스] [PCCE 기출문제] 9번 / 이웃한 칸 (1) | 2024.03.05 |
[알고리즘 - 인프런] 응급실 Queue와 객체를 이용한 풀이 (0) | 2024.02.07 |
[알고리즘 - 인프런] 공주구하기 - Queue 기본문제 (1) | 2024.02.06 |
[알고리즘 - 프로그래머스, 인프런] 2019 카카오 겨울 개발자 인턴십 코딩테스트 문제 - 크레인 인형뽑기(카카오) (1) | 2024.02.06 |