- 첫번째에 accept 되었지만, map 을 다루는 과정에서 compile 에러가 나왔고, (getOrDefault, put)
- map 에서 value 들을 가져올때는, map.getValues() 가 아니고 map.values() 였다.
- time complexity 는,
- string 개수를 N개라고 할 때 각 단어들에 대해 interate 돌기 때문에, O(N)
- string 각각의 길이를 k 라고 하면, 매 단어마다 char 로 쪼개서 정렬을 다시 했기 때문에 klogk가 든다.
- 따라서 O(Nklogk) 가 되는것 같다.
- anagram 으로 묶을때 같은 group 인지 체크하는 함수를, char array 로 바꿔서 정렬해서 확인하지 않고, 뭔가 다른방법으로 해야 성능을 높일 수 있을 것 같다.
- 정답을 보니, 첫번째는 내가 푼것과 거의 동일, 시간 복잡도 계산까지 똑같았다.
- 두번째로는, 내가 생각하지 못했던, 각 단어의 char array 를 정렬할 게 아니라, 알파벳별로 count 해서 int [26] 배열에 넣고, 단어사이에 # 같은 구분자를 넣어 string 을 만든 다음 anagram group key 로 쓴다.
- ab-> #1#1#0#0....., aab->#2#1#0#0....., 이런식으로
- 그런데 이렇게 돌려보니 속도가 더 안나온다. 복잡도는 O(Nk) 가 되는데 말이다. StringBuffer 통해 다시 String 으로 만드는게 오래 걸려서 그런가?
- 속도가 제일 좋은 건 아래와 같은 unique key 를 만드는 것이었다. 각각의 char 의 int value 를 더한것과 곱한것을 합한 것이 unique 하다니, 직관적으로 이해가 가지는 않는다.
- 기본적인 원리는 이해했고, 추측했지만, 이런 unique key 를 만드는건 아직 잘 못하겠다.
// take the sum of all values and product of all values and add together basically creating a unique hash
int sum = 1;
int total = 0;
for(int i=0; i < str.length(); i++){
int intVal = str.charAt(i);
sum = sum *intVal;
total = total + intVal;
}
sum = sum + total;
Comments
Post a Comment