목표
알파벳의 연속으로 주어진 문자열을 각 문자에 대응되는 개수순으로 문자열을 압축하기
방법
방법에는 크게 두가지가 있다. 문자열 전체를 순회해서 알파벳의 문자별로 하나씩 세는 방법과 문자열을 한번 정렬한 뒤에 알파벳을 문자별로 세는 방식이 있다. 전자는 한 문자당 문자열 전체를 순회해야하는 반면에 후자는 문자열을 정렬하는 비용을 투자하는 대신에 정렬 단계 이후에는 문자열을 한번만 순회하면 된다.
분석
전자는 시간복잡도가 O(N^2)이다. 후자는 O(NlogN + N)이다. 따라서 데이터의 크기가 무한할 때 후자가 성능이 좋다.
정리
로직 중에 컨테이너가 데이터를 전체 탐색해야하는 경우에 정렬을 먼저하자.