kkn1125/text-compress-upgrade

기존 카카오 문자열 문제에서 더 세밀하게 압축하는 알고리즘 테스트

text-compress-upgrade

기존 카카오 문자열 문제에서 대부분의 솔루션의 결과물에 대한 이슈를 종합하여 발생하는 덜 압축된 문자에 대해 테스트 케이스를 생성하고 보완하는 것이 목적.

압축 이슈

테스트 케이스

1. testasastestbobotestbobo -> test2as2testbobo 로 16이 되어야 한다.
2. testtestaaatesttestbbbbbtesttestaa -> 2test3a2test2bbb2test2a 로 23이 되어야 한다.

하지만 위 테스트를 기존 솔루션에 대입해보면 다음과 같이 덜 압축되는 것을 볼 수 있다.

1. testasas2testbobo
2. 2testaaatesttestbbbbb2testaa

물론 다른 솔루션도 있겠지만 서치해본 결과 대부분의 시험자들의 솔루션이 같은 양상이다.

대부분의 솔루션이라 함은 다음과 같은 로직을 가진다.

1. 먼저 1개 단위의 문자를 앞에서 잘라내어 이중 for문을 통해 매칭되는 문자가 있으면 count를 올린다.
2. 매칭되지 않으면 증가된 count와 문자를 result라는 빈 문자열에 쌓는다.
3. count를 초기화하고 다음 매칭될 문자로 잘라내고, 잘라낸 문자로 다시 완전탐색한다.
4. 결과로 만들어진 텍스트를 출력한다.

압축 이슈 해소 방안

압축 이슈에 대한 개선 사유

1. 대량의 문자 테스트 통과를 위해 for문과 연산을 최소화한 로직이지만 디테일한 압축이 아쉽다고 판단.
2. 효율이 좋지 않지만 최대한 디테일하게 압축하도록 개선.

1. 중복되면서 해당 문자다음으로 중복이 연속되는 문자인지 판별하여 배열에 후보군을 담음.
2. 후보군 중에서 길이가 긴 문자후보에 짧은 문자후보가 포함이 되면서 2개 이상 포함되어 있으면 탈락 시킴.
3. 완성된 후보군으로 정규식을 사용하여 카운트 및 필터 시행.
4. 필터된 후보군을 reverse하여 제일 긴 문자부터 압축시행.
5. 긴 문자가 압축되면 그 다음 짧거나 동일한 길이의 후보가 압축해도 필터를 한 후보이기때문에 두 번 압축시키는 오류를 제외함.

압축 로직 개선

압축 로직을 개선하면서 문제점을 파악하고, 해당 문제를 수정하면서 본래의 기능을 잃지 않도록 기능 보존에 대한 인식을 향상시킬수 있었음.

이전보다 효율이 떨어지지만 적은 량의 테스트 문자열에서는 큰 차이 없이 작동 가능.

압축 로직 개선 후

보다 많은 테스트케이스를 추가하여 예외사항을 찾아 보완해나가는 방식으로 리팩터링 실시 예정.

계속해서 오류를 발견하고 개선해나가고 있습니다.

텍스트기반으로 붙이는 로직 대신 토큰화해서 압축이 필요한 토큰을 계속해서 압축하는 방법으로 개발해나가고 있습니다.