[LeetCode] 49. 그룹 애너그램 Group Anagram ( 다시 풀어볼 것 )
문제 풀이 고민 : 브루트 포스 ( 전체 탐색)
(:40)
각 단어당 unique한 글자를 갖지 않을 수도 있다.
그니까, 각 단어당, 어떤 글자의 개수는 1개 이상일 수도 있다. → 문제의 조건을 보면, 하나의 strs[i]의 길이가 최대 100도 되는 것을 보아하니, 중복되는 글자가 존재한다.
- Map을 사용할까
- array를 사용할까?
지금 생각나는 풀이로는 Map을 사용하나 Array를 사용하나, 한 단어 한단어씩 비교하게 되는 풀이밖에 생각이 나지 않는다. 결국 두 경우 모두
→ 10000 x 10000 이 나올 수도 있어질 것 같다.
만약 이런식의 브루트 포스적인 접근으로 푼다면
int[][] numOfAlpha 를 두고,
- 모든 strs 에 대하여 → 각 strs[i]에 대하여, 각 알파벳의 개수를 numOfAlpha[i]에 넣어둘 수 있다.
- 그 후, numOfAlpha[i]를 numOfAlpha 전체를 loop를 돌면서 비교하는 거다.
그니까 진짜 장난 아니다. 왜그러냐면
결국 10000 + 9999 + 9...
10000x 9999 /2 → 4900 만이 나온다 → 일단 답은 나올 거라는 판단이 들었다.
- 역시 답은 나왔음
- 하지만 최악의 시간복잡도를 가진 결과가 나오게 되었음.
문제 풀이 : 개선된 풀이..
애너그램과 관련한 글을 찾아보았다. → 그렇다, 이 글자들을 정렬할 수 있다면? 비교가 매우 쉬워진다.
첫 번째로는 strs 자체를 정렬한다.
String → char[] 변환 하여 → 이 배열을 정렬 → 다시 String으로 변환 → Map에 넣는다.
- 그러면 순차적으로, 이 문자열만을 비교하면 된다. ( Java의 String 은 equals를 오버라이드하여 논리적동등비교를 하고 있으니)
- 잘 몰랐던 부분 && 궁금한 부분.
- String → char[] 로 변환하던 것 ( JAVA에서 String class의 구조를 다시 한 번 공부 해 봐야겠음 )
- toString() 과 String.valueof()의 차이 ? 어떤 차이가 있을까? 앞에거는 char[].toString() 이라는 차이일까?
- Map.values() 를 바로 ArrayList로 변환이 가능했다.
- 궁금한점 : char[] 을 비교하는 것 보다 String의 == 비교가 더 빠를까? 생산성 측면에서는 당연히 더 빠르겠지만 ( == 만으로 동등 비교가 가능하니 ), 실제로 더 빠를까? 어차피 String도 내부적으론 char[] 가 아닐까? byte[] 이라면 뭔가 달라질까??
