기존 카카오 문자열 문제에서 대부분의 솔루션의 결과물에 대한 이슈를 종합하여 발생하는 덜 압축된 문자에 대해 테스트 케이스를 생성하고 보완하는 것이 목적.
테스트 케이스
- testasastestbobotestbobo -> test2as2testbobo 로 16이 되어야 한다.
- testtestaaatesttestbbbbbtesttestaa -> 2test3a2test2bbb2test2a 로 23이 되어야 한다.
하지만 위 테스트를 기존 솔루션에 대입해보면 다음과 같이 덜 압축되는 것을 볼 수 있다.
- testasas2testbobo
- 2testaaatesttestbbbbb2testaa
물론 다른 솔루션도 있겠지만 서치해본 결과 대부분의 시험자들의 솔루션이 같은 양상이다.
대부분의 솔루션이라 함은 다음과 같은 로직을 가진다.
- 먼저 1개 단위의 문자를 앞에서 잘라내어 이중 for문을 통해 매칭되는 문자가 있으면 count를 올린다.
- 매칭되지 않으면 증가된 count와 문자를 result라는 빈 문자열에 쌓는다.
- count를 초기화하고 다음 매칭될 문자로 잘라내고, 잘라낸 문자로 다시 완전탐색한다.
- 결과로 만들어진 텍스트를 출력한다.
압축 이슈에 대한 개선 사유
- 대량의 문자 테스트 통과를 위해 for문과 연산을 최소화한 로직이지만 디테일한 압축이 아쉽다고 판단.
- 효율이 좋지 않지만 최대한 디테일하게 압축하도록 개선.
- 중복되면서 해당 문자다음으로 중복이 연속되는 문자인지 판별하여 배열에 후보군을 담음.
- 후보군 중에서 길이가 긴 문자후보에 짧은 문자후보가 포함이 되면서 2개 이상 포함되어 있으면 탈락 시킴.
- 완성된 후보군으로 정규식을 사용하여 카운트 및 필터 시행.
- 필터된 후보군을 reverse하여 제일 긴 문자부터 압축시행.
- 긴 문자가 압축되면 그 다음 짧거나 동일한 길이의 후보가 압축해도 필터를 한 후보이기때문에 두 번 압축시키는 오류를 제외함.
압축 로직을 개선하면서 문제점을 파악하고, 해당 문제를 수정하면서 본래의 기능을 잃지 않도록 기능 보존에 대한 인식을 향상시킬수 있었음.
이전보다 효율이 떨어지지만 적은 량의 테스트 문자열에서는 큰 차이 없이 작동 가능.
보다 많은 테스트케이스를 추가하여 예외사항을 찾아 보완해나가는 방식으로 리팩터링 실시 예정.
계속해서 오류를 발견하고 개선해나가고 있습니다.
텍스트기반으로 붙이는 로직 대신 토큰화해서 압축이 필요한 토큰을 계속해서 압축하는 방법으로 개발해나가고 있습니다.