Frequency Queries

생각한 것

특정 키와 그 키의 빈도수를 표현하기 위해서는 역시 map 구조가 잘 어울린다고 생각했고 <키, 빈도> 형태의 hashmap을 만들어서 입력값을 받아 넣어주었다. 그런데 값이 잘 들어가지 않거나 타임 아웃이 나서 실패했다.

개선

결국 필요한 출력값은 어떤 키가 됐던 간에 빈도수만 맞으면 결정된다. 즉 빈도수만 생각하는 자료구조를 하나 더 만들어주면 된다고 생각했다. 그래서 <빈도 수, 빈도수의 빈도수>를 가지는 hashmap을 하나 더 만들어서 값을 넣고 뺄때 함께 계산해줬다.

결말

타임아웃은 여전히 난다. 아직도 완전히 풀고 있지 못한 문제다... 입력 개수가 10만개가 넘어가니 타임아웃이 난다. 아무래도 map.containsKey() 메소드가 순차적으로 값을 찾다보니 그런 것 같다. 그렇다면 특정 key나 value를 한번에 찾으려면 어떻게 해야할까. 배열로 처리하려고 하니 java heap size 초과로 프로그램이 죽어버린다... 추후에 해결하게 된다면 이 글을 수정하겠다.