왜 고생을 사서 하는가? 젊기 때문이겠지.. 끄응.
오늘은 리트코드 49번 문제를 풀어보았다. 사실 혼자서는 못 풀었고 구글과 여러 스택오버플로우 글과,, 챗 지피티와.. 이런 다양한 도구의 도움이 필수적이었다.
풀어야 하는 문제는 다음과 같다. 입력값과 출력값을 먼저 보여드리겠습니다.
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
입력으로 strs 안에 다양한 단어들이 나온다. 아웃풋으로는 그룹이 지어져 있는데 nat, tan은 같은 알파벳 종류로 구성이 가능한 친구들이다. 가족과 같은 것이지. 반면 bat 같은 경우는 a,t,b 가지고 구성할 수 있는 알파벳 단어가 strs 안에 오직 혼자이다. 그래서 홀로 외롭게 앉아 있는 것이다.
내가 알게된 이 문제를 해결하는 접근법은 두 종류이다.
1. 개별 단어를 정렬하고, 정렬했을 때 같은 값들인 친구들끼리 묶어서 출력한다.
2. 고정된 26개의 원소를 갖는 리스트를 만들어서, 해당 알파벳에 체크해서 이걸 키로 만들어 사용한다.
나는 2번으로 했다.
만약 단어가 'abc' 이런게 나왔다면, 내 26 사이즈 배열은 [1,1,1,0,....0] 앞의 3 개 원소가 1이고 나머지는 0인 아이가 된다.
그렇게 해서 나중에 join 해서 문자열로 만든 뒤에 비교하면 되겠다 했는데 여기에서 고려하지 못한 부분이 있었다.
join('') 이렇게 쓰게 되니까, 중복키 충돌이 발생했다. 그래서 에러가 난 것 같다.
[1,0,0,0,1] 이 있을 수 있고 [10,0,0,1] 이 있을 텐데, 그냥 묶어버리면 서로 다른 배열인데 같은 값이 되어버린다 10001 이렇게.
그래서 join("#") 을 사용했다. 사실 나는 돈을 좋아해서 join("$") 이렇게 써볼라고 했는데 $ 같은 경우는 special character, 이미 용도가 있는 reserved 라서 그런지 안된다고 했다.
class Solution {
List<List<String>> groupAnagrams(List<String> strs) {
Map<String, List<String>> group = {};
for (var str in strs) {
var filled = List.filled(26,0);
for (int i = 0; i<str.length; i++) {
filled[str.codeUnitAt(i)-'a'.codeUnitAt(0)]++;
}
String key = filled.join('#');
if (!group.containsKey(key)) {
group[key] = [];
}
group[key]!.add(str);
}
return group.values.toList();
}
}
-끄읕-