409. Longest Palindrome

https://leetcode.com/problems/longest-palindrome/

1) Original
문자는 ascii 번호로 되어 있기 때문에 이를 저장할 해시맵 map[256] 을 준비한다.
그리고 각 문자가 몇개 나오는지 카운트한다.
또한 256 사이즈를 다 스캔하기에는 번거로울 수 있으니, key를 unordered set(동일한 키 추가 방지) 으로 저장해준다. (이건 이 문제의 경우, 알맞지 않은 방법이었다)

이제 카운트 숫자가 짝수인지 홀수인지 판단한다.
만약 짝수라면 그대로 더해주면 된다. 하지만 홀수라면, 그대로 더해주면 안된다.
Palindrome은 단 한번의 홀수만 허용이 가능하다. 따라서 나는 이를 위해 sig라는 bool 을 만들었고,
한번만 허용가능한 홀수가 나왔을 때, sig를 false로 업데이트해준다. 
sig가 true일 경우 length에 홀수를 그대로 더해주어도 괜찮고,
sig가 false일 경우 length에 홀수 - 1, 가장 큰 짝수를 더해야주야한다.

결과로 3ms 정도의 속도가 나온다.

사실 나는 map structure을 사용하는 것을 별로 선호하지 않는다.
아래는 map을 사용해 똑같은 알고리즘을 구현한 것인데, 실험한 바로는 저장공간도 비슷하거나 좀 더 많이 필요하면서,
더 느리다. 이유는 map은 array에 접근하는 것에 비해, 캐시효율이 좋지가 않고, find를 계속 해야하기 때문인 것 같다.

동일한 이유에서, unordered_set을 사용하지 않고, 256개의 array를 그냥 스캔하는 방식으로 돌려봤다.

결과는 0ms 훨씬 빠르다.