[Leet Code] 49. Group Anagrams
문제
문자열들의 배열 strs가 주어질 때, 애너그램을 함께 그룹지어라. 정답은 여러 순서로 반환할 수 있다.
애너그램은 일반적으로 원본 문자들을 정확히 한 번씩 전부 사용하여, 다른 단어나 구문의 문자를 재배열 함으로써 만들어진 단어나 구문이다.
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^40 <= strs[i].length <= 100strs[i]는 영소문자로 이루어져 있다.
접근 방법
사실 도저히 모르겠어서 discussion을 참고하여 문제를 풀기는 했다. 그래도 내가 discussion을 보기까지 어떤 생각을 했는지 적도록 하겠다.
막무가내로 그룹핑
Example 1을 예시로 했을 때, 말 그대로 맨 첫 번째 문자열인 “eat”의 문자 3개로 나올 수 있는 조합을 전부 만든다. 그리고 그 조합들과 배열의 요소를 비교하여 조합과 일치하는 배열의 요소끼리 그룹핑한다. 그렇게 하면 문자 3개의 단어는 조합의 개수가 $3!$ 일 것이고, 100개의 문자를 가진 단어는 $100!$의 조합을 가질 것이다.
이 경우의 수를 모두 연산하는 것도, 해당 조합과 배열의 요소를 일일이 비교하는 것도 성능이 바닥을 기어다닐 것 같아서 다른 방법을 찾았다.
사용된 알파벳의 개수를 이용
Example 1에서는 e가 3개, a는 6개, t는 6개… 등이 사용되었다. 여기서 나는 가장 많이 사용된 알파벳 3개를 가지고 단어를 조합할 생각이었다. 그런데 만약 단어의 길이가 일정하지 않을 수도 있거니와, 가장 많이 사용된 알파벳을 추출하여 단어를 조합한다 해도, 그게 꼭 배열의 요소란 법은 없어서 이 방법도 제외했다.
사용된 알파벳을 인덱싱
이게 풀이와 가장 가까운 생각이었다. a-z까지의 위치를 나타낼 배열을 만들고, 한 단어에서 사용된 알파벳은 1로 바꿔버리는 것이었다. 즉, “eat”라면
alphabetPosition = { 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }; // a, e, t
a-z 위치 배열은 다음과 같은 값을 가질 것이다. 그런데 이렇게 인덱싱을 하고 난 이후에 이 배열을 어떻게 이용할지에서 막혔다.
사용된 알파벳을 인덱싱 .from discussion
discussion에서 한 유저의 풀이를 봤는데, 사용된 알파벳을 인덱싱 하는 방법이 나와 달랐다.
나는 인덱싱을 배열로 처리했지만, 해당 유저는 내가 한 방식의 배열 요소들을 전부 문자열로 만들어 HashMap의 키로 사용하는 방법을 택했다. 예시로 아까 만든 alphabetPosition의 요소를 그 유저의 방식대로 인덱싱하면, 키를
key = "1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0" // #는 이전 알파벳과 다음 알파벳을 구분하는 역할
와 같이 만들어 사용할 수 있다. 그러면 eat의 애너그램인 tan, tea, ate 또한 같은 키를 가질 것이다. 이후에는 ArrayList의 값 부분에 해당 문자열들을 추가해주면 된다.
풀이
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
ArrayList<List<String>> anagrams = new ArrayList<List<String>>();
HashMap<String, List<String>> anagramGroups = new HashMap<String, List<String>>();
for (String str : strs) {
int[] alphabetCount = new int[26]; // 알파벳 개수만큼 배열 할당
for (char c : str.toCharArray())
alphabetCount[c - 'a']++; // 사용된 알파벳 자리에 사용 횟수 추가
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
sb.append(alphabetCount[i]);
sb.append("#"); // 이전 알파벳과 다음 알파벳을 구분
}
String anagramKey = sb.toString();
anagramGroups.putIfAbsent(anagramKey, new ArrayList<String>());
anagramGroups.get(anagramKey).add(str);
}
anagrams.addAll(anagramGroups.values());
return anagrams;
}
}
- Runtime: 28ms
- Memory: 61.1MB
- 함수
map.putIfAbsent(key, value): 만약 현재 키가 존재할 경우 값을 반환하지만, 키가 없을 경우 키와 값을 map에 저장 후 null 반환list.addAll(ArrayList): 주체가 되는 ArrayList(list)에 다른 ArrayList 데이터를 통째로 붙임
List vs ArrayList
자바를 오랜만에 해서… ArrayList 선언을 무심코 List로 했는데, 선언부에는 문제가 없었지만 ArrayList의 함수를 호출했을 때 인터페이스는 어쩌구 하는 오류를 봤었다. 그걸 보고 아차 싶어서 바로 ArrayList로 바꿔서 코드를 실행했다. 여기서 든 생각이 “자바에 List라는 자료형이 있네?”였다. 그래서 List와 ArrayList의 차이가 뭘지를 찾아봤다.
List는 인터페이스 ArrayList는 클래스
개념적으로는 이런 차이가 있다. 여기서 하나 재밌는 게, List의 namespace는 System.Collections.Generic이고, ArrayList의 namespace는 System.Collections라는 점이다. 즉, List는 Generic의 성격을 가지고, ArrayList는 그렇지 않다는 점이 가장 큰 차이인 것 같다. 여기서 Generic은 클래스 내부에서 지정하는 것이 아니라, 외부에서 사용자에 의해 지정되는 것을 의미한다.예시로 List를 보면
// List
List<> list = new ArrayList<>();
List<> list = new LinkedList<>();
// ArrayList
ArrayList<> arrayList = new ArrayList<>();
ArrayList<> arrayList = new LinkedList<>(); // error
// LinkedList
LinkedList<> linkedList = new LinkedList<>();
LinkedList<> linkedList = new ArrayList<>(); // error
이렇게 List 자료형의 경우, List로 선언한 인스턴스를 ArrayList나 LinkedList로 변환할 수 있다. 반면에 error 주석 부분인 ArrayList -> LinkedList이나 LinkedList -> ArrayList는 정상적인 실행이 불가능하다.
참고 링크:
댓글남기기